union find

D - 道路の老朽化対策について ~サイズ付きUnion Find~

Quiz https://atcoder.jp/contests/abc040/tasks/abc040_d AC (verified) https://atcoder.jp/contests/abc040/submissions/8891107 解説 editorialの通りですが、ポイントとしては「橋の構築」と「クエリ」を同じvectorに入れてyearでソートした後、yearの…

最小全域木 MST (minimum spanning tree)

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A&lang=jp AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3589709#1 解法 Kruskal法を使う 辺を列挙し、コストの軽いものから見ていって非連結じゃない頂点をつなぐなら採…

No.74 貯金箱の退屈

Quiz https://yukicoder.me/problems/no/74 Submit https://yukicoder.me/submissions/339953 解法 1枚だけでflipできるコインを調べておく 2枚flipのとき a, bを一緒にflipできるなら、Union Findでunite(a, b)しておく 「一緒にflipできるグループ」ごとに…

No.416 旅行会社

Quiz https://yukicoder.me/problems/no/416 Submit https://yukicoder.me/submissions/339563 解法 破壊される辺以外を張っておく 破壊クエリを逆から読みながらその辺を復活させていく 木がつながったかはUnion Findで管理する 辺を繋げる前に、今回の接続…

F - Asya And Kittens

Quiz https://codeforces.com/contest/1131/problem/F Submit https://codeforces.com/contest/1131/submission/50398023 Note 問題文の図の通り、union find木などで結合していく グループ毎にメンバー一覧を持っておく 結合した時、グループAとグループBの…