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

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

クエリ(グラフ上)

AtCoder ABC 235 E - MST + 1 (水色, 500 点)

MST の理解が問われる面白い教育的問題! 問題へのリンク 問題概要 頂点数 、辺数 の連結な重み付き単純無向グラフ が与えられる。なお、各辺の重みはすべて互いに異なることが保証されている。 の最小全域木を とする (一意に定まることが示せる)。 このグ…

AtCoder ABC 304 E - Good Graph (緑色, 475 点)

Union-Find 慣れしていれば解きやすい! 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフ が与えられる。 組の頂点対 について、どの頂点対間のもパスがないグラフを良いグラフと呼ぶことにする。 与えられるグラフ は良いグラフである。 このグラ…

AtCoder ABC 302 E - Isolation (緑色, 425 点)

「要素の削除」をする必要がある場合は set が使えたりする 問題へのリンク 問題概要 最初、頂点数 、辺数 のグラフがある。 このグラフに対して次の 個のクエリに答えて、毎クエリ後にその時点での「グラフの孤立点の個数」を出力せよ。 クエリタイプ 1 (1 …

AtCoder ABC 280 F - Pay or Receive (青色, 500 点)

重み付き Union-Find が使える鮮やかな楽しい問題! 問題へのリンク 問題概要 頂点数 (頂点番号が ) のグラフが与えられる。このグラフには 組の辺があり、 組目の辺は、 頂点 から頂点 へと、長さ の有向辺 頂点 から頂点 へと、長さ の有向辺 となっている…

AtCoder ABC 014 D - 閉路 (試験管青色)

木上のパスに関する問題!! LCA で解決できる典型問題 問題へのリンク 問題概要 頂点数 の木が与えられる。次の 個のクエリに答えよ。 各クエリでは木上の 2 頂点 が与えられる 木に辺 を仮に追加したとすると、閉路が 1 個形成される その閉路に含まれる辺…

Codeforces Round #673 (Div. 1) D. Graph and Queries (R2600)

いろんな方法がありそう。Union-Find のマージ過程を表す木でやったけど、ほかにも Undo 付き Union-Find を使うなど 問題へのリンク 問題概要 頂点数 、辺数 のグラフが与えられる。初期状態では各頂点に という値がついている (すべて 1 以上で disjoint)…

AtCoder ABC 120 D - Decayed Bridges (水色, 400 点)

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

AtCoder ARC 039 D - 旅行会社高橋君 (試験管橙色)

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

JOI 本選 2012 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(int n) : par(n), rank(n, 0</int></algorithm></map></queue></vector></iostream>…