けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Union-Findのマージ過程を表す木を考える

Codeforces Grakn Forces 2020 G. Clusterization Counting (R2700)

めちゃ好きだけど、実装重い 問題へのリンク 問題概要 頂点の重み付き無向完全グラフが与えられる。各 に対して、 頂点集合を 個の互いに disjoint な集合に分割する方法であって どの同族辺 (両端点が同一のグループに属する辺) の重みも、どの異族辺 (両端…

CODE THANKS FESTIVAL 2017 H - Union Sets (600 点)

たくさんの方法がとれる超教育的な問題なので、たくさんの方法で解いてみたん。 問題へのリンク 問題概要 の 個の集合がある。 と とを併合する という操作が 回行われた。以下の 個のクエリに答えよ: と が何回目の操作後にはじめて一緒のグループになった…

AtCoder AGC 002 D - Stamp Rally (橙色, 1000 点)

部分永続 Union-Find 木の練習をした。 問題概要 (AGC 002 D) N 頂点 M 辺の無向グラフがあります。 グラフは連結です。以下の Q 個のクエリに答えよ: 頂点 x, y が与えられ、「x と y を含む z 個の頂点からなる集合に含まれる頂点の番号の最大値」の最小値…

JOI 本選 2011 E - JOI 国のお祭り事情 (AOJ 0575, 難易度 10)

並列二分探索が想定ではなさそうだけど、並列二分探索のいい練習問題になったん!!! 問題へのリンク 問題概要 制約 解法 #include <iostream> #include <vector> #include <queue> #include <map> #include <algorithm> using namespace std; struct UnionFind { vector<int> par, rank, sz; UnionFind(in</int></algorithm></map></queue></vector></iostream>…

AtCoder ARC 098 F - Donation (赤色, 1000 点)

本番中に解きたかった... ARC 098 F Donation 問題概要 N 頂点 M 辺の連結な単純無向グラフがあります。 頂点 i には二つの整数 Ai, Bi が定められています。 このグラフ上で次のようなゲームをします。 初めに、W 円を持った状態で好きな頂点に立つ。 ただ…