並列二分探索
Union-Find
永続化
永続Union-Find
並列二分探索
二分探索
クエリ処理問題
データ構造
クエリ先読み
クエリの平方分割
平方分割
マージテク
AtCoder
unrated公式コン
AtCoder600点
Union-Findのマージ過程を表す木を考える
たくさんの方法がとれる超教育的な問題なので、たくさんの方法で解いてみたん。 問題へのリンク 問題概要 の 個の集合がある。 と とを併合する という操作が 回行われた。以下の 個のクエリに答えよ: と が何回目の操作後にはじめて一緒のグループになった…
永続化
データ構造
Union-Find
永続Union-Find
並列二分探索
二分探索
クエリ処理問題
平方分割
クエリの平方分割
最大値の最小化
AtCoder
AGC-D
AtCoder1000点
橙色diff
Union-Findのマージ過程を表す木を考える
部分永続 Union-Find 木の練習をした。 問題概要 (AGC 002 D) N 頂点 M 辺の無向グラフがあります。 グラフは連結です。以下の Q 個のクエリに答えよ: 頂点 x, y が与えられ、「x と y を含む z 個の頂点からなる集合に含まれる頂点の番号の最大値」の最小値…
並列二分探索
Union-Find
二分探索
最大値の最小化
データ構造
クエリ処理問題
Dijkstra法
最短路問題
グラフ問題
クエリ(グラフ上)
前処理
AOJ
AtCoder
JOI本選
JOI
Union-Findのマージ過程を表す木を考える
JOI難易度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>…