hiko3r https://blog.hatena.ne.jp/hiko3r/ Hoi_koro memo https://hoikoro.hatenablog.com/ AtCoder AGC agc002.contest.atcoder.jp 問題 グラフ中の辺に番号がつけられている。クエリが与えられるので、「辺のみを残した部分グラフ中で頂点集合またはから到達可能な頂点が個以上になる」ようなの最小値を各について求めよ。 解法 愚直にやるなら各クエリに対してN要素のUnion-Findを作り、辺1から順に両端の頂点をuniteしていく。到達可能な頂点数（とが非連結なら）が以上になる時の辺番号が答えとなる。でTLE。 愚直手法ではuniteしてを調べる操作をクエリあたり回もループしているので、平方分割によりこれを減らせば間に合う。あらかじめまでuniteした個のUnion-Findを構… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fhoikoro.hatenablog.com%2Fentry%2F2017%2F12%2F14%2F040750" title="AtCoder AGC002 D Stamp Rally - Hoi_koro memo" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://chart.apis.google.com/chart?cht=tx&chl=%7BT%7D Hatena Blog https://hatena.blog 2017-12-14 04:07:50 rich https://hoikoro.hatenablog.com/entry/2017/12/14/040750 1.0 100%