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がもったいない。