https://beta.atcoder.jp/contests/arc063/tasks/arc063_c 範囲求めて木の根から決めていけば良い。証明が少しあやふやで本番WAしたら自信無くして通せなさそう。
https://arc079.contest.atcoder.jp/tasks/arc079_d 丁寧丁寧丁寧にやったのでバグらせなかったけどうーん遅いなぁ。ループ内の値が2択になるのでDPすれば良い。
https://agc011.contest.atcoder.jp/tasks/agc011_c 二部グラフかどうか判定すれば良いんだけどそれをバグらせるという…
bool loop(int v, int k) { used[v] = true; bi[v] = k; bool ok = true; rep(i, 0, sz(G[v])) { int n = G[v][i]; if(!used[n]) { if(!loop(n, 1 - k)) { ok = false; // don't return false } } else { if(bi[v] == bi[n]) ok = false; } } return ok; }
ちゃんと全部の連結成分についてvisitしないといけません。途中でfalseをreturnするとバグります。