Codeforces Round 1046 (Div. 1)

　D1まで四完。D2は分かったのに実装間に合わず。あと一分あれば間に合っていた気がするので悔しい。

コンテストへのリンク

コンテスト後のツイート

C サイクルに含まれない部分は*Vして消しておく。その上で、橋で分解し、分解した成分ごとに二部グラフかどうかを見る。二部グラフなら全部一緒。そうでなければ全部0
D1 [1]*100000をきき、x～yに絞る。その後、x 1 x 2 ...と聞く。

— titia (@titia_til) August 28, 2025

D2. From the Unknown (Hard Version)

　D1と同じ発想で解ける。

　最初[125]*10000と聞く。（この125とか10000は色々試して探す）

　0のときは[1]*15000で決定できる。

　そうでないときはD1と同じようにやる。同じ値が連続して15000/2個以上出てたらクエリの長さが間に合わないが、この値だと間に合っている。

　この最後のパートをD1と全く同じように書いていたのがダメでした。クエリ回数を抑えるため、同じ数字が返ってくるものの個数だけ使わなくてはいけなかった。これでAC。