B を見るとクエリ数の制限がかなり厳しく、そもそも i,j 本目の辺を含むクエリ集合が異なることすらちゃんとやらないと満たせなさそう。とりあえず i を 2 冪で表したとき bit が立っているところだけクエリ集合に入れてみるとそこそこよさそうな感じだが、辺を特定することは出来ない。そこで、i 本目の辺が含まれる回数を固定しつつ i,j 本目の辺を含むクエリ集合が異なるを満たすために、binom(2n,n) テクを使う(このテクニックなんと呼べばいいのだろうか...)

2 進数の変わりに、0 を k 個、1 を k 個並べた列としてあり得るものをそれぞれの辺に相異なるように割り振り、それぞれの辺では bit が立っているところだけクエリ集合に入れると辺で結ばれている頂点の組 (u,v) は k 回同じ連結成分に現れ、それ以外の頂点対が同じ連結成分に現れるのは k 回未満となる。(辺に割り振られた列が相異なることに注意せよ。)

よって、あとは愚直に探索すれば O(n^2 log n) となり小課題 1,2 の満点が得られる。これだと小課題 3 の制約が n <= 2^17 であるため届かない。そこで、1 個の頂点と辺で繋がれている頂点は O(n) かければ発見可能であるため、これを利用して自分が属する連結成分のサイズの総和が最も大きい頂点をこれを利用して取り除き、残りを再帰する変わった重心分解のようなことを試みる。また、連結成分のサイズの 2 乗和が小さくなってきたら愚直に切り替えることにする。ただこれだと TLE してしまい中々通せず 2 時間半が経過。一度切り上げて A,C を見ることにする。(ジャッジにコードテストが付いているのだが、そのコードテストで使われるジャッジの入力形式が配られたものとは違うという罠にかかってしまった...)

A は解法は問題文を読んで少し考えたときに大体分かっていて、途中で出くわしてからも一緒に動くことにすると結局グラフ上のある 1 点で全員が揃うことにしてよい。よって、それぞれの人に対して dijkstra をしてそれぞれの頂点までの距離を求めて、辺上は折線の max になるので折線を線分に分解してそれぞれの線分の区間で処理をすればよい。この線分に分解して max を取る部分でバグらせてしまい、40 分程で満点となった。

C はいかにもやばそうな問題文だが小課題 3 までは愚直 dp が許されそうだったのでとりあえず取る。小課題 4 が謎だがランダムということで小課題 3 の dp を直前の max 60 ケースだけ遷移するコードを投げると通ってしまった。2 ケースしか入ってないしなんだこの小課題は...(ここまでで 20 分程)

C の残りはやばそうだったので B に戻ってみる。愚直に切り替えていたところをかなり条件を厳しくしてみると TLE していたケースが通り他のケースで MLE となった。希望が見えたので頑張ってメモリ節約してみると小課題 3 も AC して満点を獲得した。ここで 1 時間が消費された。後で解説を見てみると上手く条件を決めて再帰していた...

C の残りをあと 30 分で考えることにする。小課題 5 のクエリ回数があまりにも厳しいので幅 1,2 の部分しかクエリを飛ばさないことにしてみた。だが AC が取れないので色々試してみるが落ちないのでよくわからない。実はただバグらせているだけだったが、コンテスト中に通すことは出来なかった。(17 分程遅れて AC)

100-100-64=264 となった。C が後 21 点はバグらせていなければ取れたはずなので悔しいが、B が計算量保証がない中満点が取れたのはかなり運が良かったと思う。C の満点は一体なんなんだ...