TopCoder SRM 782 : Div1 Hard PaintItBlack

900ptでもいい気はする。
https://community.topcoder.com/stat?c=problem_statement&pm=15975&rd=17900

問題

N頂点の連結無向グラフが与えられる。
各頂点は白黒で塗ることが可能で、初期状態では全頂点白で塗られている。

頂点Uから初めたパスを考える。
移動先の各頂点において、色を白黒反転させる、ということを繰り返し、パスがUを終端としてかつ全頂点黒となるようにしたい。
同じ辺・頂点を繰り返し通ってもよいが、総長は5N以下にしたい。
そのような塗り方は可能か。

解法

まずUを根とする木の場合を考える。
U以外の白頂点からなる部分グラフにおいて、葉まで行って戻ってくる、ということを繰り返すと、葉が黒くなり、Uが白黒反転するという状態になる。
すなわちU以外の頂点数が奇数、全体が偶数なら、全体を木とみなした状態ですべて黒くすることができる。
実際は毎回Uに戻るのは無駄なので、子頂点以下を全部黒くしたら親に戻る、という手順を繰り返し葉から黒くしていこう。
こうするとU以外は全部黒くでき、その手順は4N回以下である。

問題は全体の頂点数が偶数の場合である。
この時は、奇数の閉路長の閉路を1つ求めよう。
探索中、その閉路に差し掛かったら1回だけそこを1周する。
そうすると、もともと黒くすべきだった頂点数が奇数個だけ減り、上記アルゴリズムが利用可能になる。
奇数の閉路長の閉路がなければ解なし。

vector<int> E[1010];
int did[1010];
vector<int> GL,R,V;
int col[1010];
int D[1010];
int turn;

class PaintItBlack {
	public:
	
	int dfs(int cur,int pre) {
		if(did[cur]==1) {
			if(GL.empty() && D[cur]==D[pre]) {
				int i;
				for(i=V.size()-1;i>=0;i--) {
					GL.push_back(V[i]);
					if(V[i]==cur) break;
				}
			}
			return 0;
		}
		col[cur]^=1;
		did[cur]=1;
		V.push_back(cur);
		R.push_back(cur);
		if(cur!=pre) D[cur]=D[pre]^1;
		
		if(turn==1 && cur==GL.back()) {
			FORR(g,GL) R.push_back(g), col[g]^=1;
		}

		FORR(e,E[cur]) if(e!=pre) {
			int r=dfs(e,cur);
			if(r) {
				R.push_back(cur);
				col[cur]^=1;
				if(col[e]==0) {
					R.push_back(e);
					R.push_back(cur);
					col[e]^=1;
					col[cur]^=1;
				}
			}
		}
		V.pop_back();
		return 1;
	}
	
	vector <int> findWalk(int n, int u, vector <int> a, vector <int> b) {
		int i;
		FOR(i,n) E[i].clear();
		GL.clear();
		
		FOR(i,a.size()) E[a[i]].push_back(b[i]),E[b[i]].push_back(a[i]);
		
		ZERO(col);
		ZERO(D);
		ZERO(did);
		R.clear();
		V.clear();
		turn=0;
		col[u]=1;
		dfs(u,u);
		cout<<col[u]<<endl;
		if(col[u]==0) {
			if(GL.empty()) return {};
			ZERO(col);
			R.clear();
			V.clear();
			ZERO(D);
			ZERO(did);
			turn=1;
			col[u]=1;
			dfs(u,u);
			assert(col[u]==1);
			
		}
		return R;
		
	}
}

まとめ

閉路つかってどうにかするところまでは行ったが、本番偶奇まで詰める時間がなかった。
ほんとMediumがもったいない。