JOI難易度10
面白かった。 問題へのリンク 問題概要 人がいて、それぞれ「スパイ」か「非スパイ」かのどちらかである。 人のうち、何人かについてはスパイかどうかが予めわかっている ( で与えられる)。 個の証言がある。各証言は人 が証言者によってなされ、「人 はスパ…
並列二分探索
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(int n) : par(n), rank(n, 0</int></algorithm></map></queue></vector></iostream>…