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

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

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

AtCoder AGC 002 D - Stamp Rally (1000 点)

並列二分探索が想定ではなさそうだけど、並列二分探索のいい練習問題になったん！！！ 問題へのリンク 問題概要 制約 解法 #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>…

JOI 2011 本選 E - JOI 国のお祭り事情 (AOJ 0575)