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

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

クエリ(グラフ上)

AtCoder ABC 120 D - Decayed Bridges (400 点)

これまたすごく教育的な問題!!!!!!!!! UnionFind 木の基本的な使い方 (連結成分のサイズ獲得含む) クエリを先読みしておいて逆順に処理 (多くのクエリ先読み問題ではもっと変な順番で処理したりする) 差分のみ更新する考え方 といったあたりを学ぶ…

AtCoder ARC 039 D - 旅行会社高橋君

二重辺連結成分分解ライブラリを整えた。 問題へのリンク 問題概要 N 頂点, M 辺の無向単純グラフにおいて、以下の Q 個のクエリに答えよ。 A B C: A から出発して B に行くウォークと、B から出発して C に行くウォークの組のうち、辺を共有しないものがあ…

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

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