Open customaddone opened 2 years ago
customaddone
commented
2 years ago 後ろからUF 辺が１本ずつ減っていく は後ろから見ると 辺が１本ずつ増えていく になる UnionFindが使える https://atcoder.jp/contests/abc120/submissions/14883836 D - Decayed Bridges 頂点が封鎖される とは その頂点を端点に持つ辺が封鎖される ということ https://atcoder.jp/contests/arc056/submissions/18632286 B - 駐車場
customaddone
commented
2 years ago マージテク 連結成分xに属するもののうちラベルがyのものの個数をオンラインクエリで答える サイズが小さいものを吸収 をやるといい https://atcoder.jp/contests/abc183/submissions/18205590 F - Confluence ラベルxかつラベルy（オンラインクエリではない）ものはマージテクしなくても解ける 二次元dictに打ち込む https://atcoder.jp/contests/abc049/submissions/18641386 D - 連結 グラフ上の移動 途中で合流する場合にはマージテクによりNlogNに抑えられる https://atcoder.jp/contests/abc212/submissions/29391547 F - Greedy Takahashi 逆に各数字にどのインデックスが対応しているかを持てばいい あとはマージテク https://codeforces.com/contest/1620/submission/148972689 E. Replace the Numbers
customaddone
commented
2 years ago 最小全域木 無理やり最小全域木の問題にできる https://atcoder.jp/contests/tkppc4-2/submissions/20465407 E - 引きこもり 頂点0の次数がDになるような全域木を求める 0が絡む辺とそれ以外とで分けておく 前処理 まず0が絡む辺以外で結んでいく 次に0が絡む辺についてnot sameなら結ぶ（絶対必要なもの） 答え作成 まずprimaryなものだけ結ぶ、Dが余ったら0が絡む辺について適当なものを結ぶ その次に0が絡む辺以外で結んでいく https://codeforces.com/contest/1133/submission/153188400 F2. Spanning Tree with One Fixed Degree 最小全域木を作ろう 最小全域木は短い辺から繋げられるだけつなぐもの https://atcoder.jp/contests/abc210/submissions/24334328 E - Ring MST https://atcoder.jp/contests/code-festival-2016-qualb/submissions/17841454 C - Gr-idian MST 候補は自分で2(N - 1)個生成する https://atcoder.jp/contests/abc065/submissions/14946081 D - Built? 超頂点その2 https://atcoder.jp/contests/arc029/submissions/16279343 C - 高橋君と国家 1 ~ rまで全部flipできるか？は半開区間l-rをunionしていって1とN+1が同じグループか？ 1, 2...を個別にflipできるか？は同様にunionしていって全てunionできているか aiを求める最小コストは頂点iとi+1との最短パスで求まるO(NlogN) 実際にaiを求める場合はiからスタートして進む:プラス、戻る:マイナスでやればいい https://atcoder.jp/contests/abc238/submissions/29100025 E - Range Sums
UnionFind データのグループ化を素早く行う not sameな頂点をN-1回つなげるとN頂点の木になる UnionFind + スタック芸 https://atcoder.jp/contests/acl1/submissions/18374339 A - Reachable Towns グラフの問題になる G の各辺に対して、端点のうちどちらかを光らせることができる。光る頂点の個数の最大値は？ 木かそうではないかは超頂点を使って検出 https://atcoder.jp/contests/arc111/submissions/19311683 B - Reversible Cards 距離が一定以下の頂点または壁をつなぐ 上の壁と下の壁は連結してるか？ https://atcoder.jp/contests/abc181/submissions/21491366 F - Silver Woods 逆Union-Find n頂点n(n-1)/2本辺のスターグラフからM本取り除いてできるグラフの連結成分の個数は何個かという問題 L:今まで未探索の頂点とすると L内にuと繋がってない頂点はいくつあるか（最高len(u)個) つながってるものは新たにuにする 繋がってないものが新たなuになる こうすることでLを何回も探索するけど総量はO(N+M)で抑えられる https://codeforces.com/contest/920/submission/162415966 E. Connected Components?