二重頂点連結成分分解して得られる Block-Cut 木のクエリに答えていく問題。 問題へのリンク 問題概要 頂点数 、辺数 の連結な単純無向グラフが与えられる。次の 回のクエリに答えよ。 【クエリ】 各クエリでは 2 頂点 が与えられる。 個の頂点のうち、次の…

とても面白かった。場合分けを詰め切るが大変だった。 問題へのリンク 問題概要 橋がただ 1 つだけ存在するような連結で単純な無向グラフをハシポンとよぶ。 頂点数 、辺数 の連結で単純な無向グラフが与えられる。このグラフに辺を追加することで、ハシポン…

Block-Cut 木を試すのにすごくいい問題！ 問題へのリンク 問題概要 頂点数 、辺数 の連結な無向グラフが与えられる（単純とは限らない）。頂点 には、重み がついている。各頂点について、以下の問に答えよ。 【問】 その頂点を除外したグラフを考える。この…

すごく面白い問題だった！ 二重頂点連結成分分解からの Block-Cut 木ライブラリを試す目的で解いてみた。 問題へのリンク 問題概要 二次元平面上に 個の点がある。各点について、次の問に答えよ。 その点を除去した上で、各点に対応する頂点数 のグラフを考…

面白かった！ 解説 AC した！ 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。このグラフの辺の順列であって、次の条件を満たすものを 1 つ求めよ（なければ -1 を出力せよ）。 【条件】 頂点数 、辺数 のグラフに対して、上記の順序…

二重辺連結成分分解とか low-link とか色々考えたけど、結果的に最後は「ただ DFS 木を作るだけ」になるという、すごく印象的な問題！ 問題へのリンク 問題概要 以上 以下の整数からなるサイズ の 2 つの数列 、 が与えられる。 今、0 と 1 のみからなるサイ…

Union-Find や、DFS、BFS などで解ける問題ですね。 問題へのリンク 問題概要 頂点数 、辺数 の連結な単純無向グラフ が与えられます。 グラフ の辺 が橋であるとは、その辺を除去したときに、グラフが連結でなくなることを指すものとします。 グラフ におい…

あの激熱展開を繰り広げた会津合宿北大セットの E 問題。 「橋以外を壊した方がいいケースもある」ということに終盤間際で気づいてからの、残り 14 秒で通せたのは感動した！！！！！！！ こたつがめさん・シンヤカトーありがとーーー コンテストでは、「二…

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

二重辺連結成分分解と聞いて 問題へのリンク 問題概要 n 頂点 m 辺の連結な無向単純グラフが与えられる。 2 点 s, t を選んで、「その辺を壊したら s と t とが繋がらなくなる」ような辺をすべて壊すことを考える。 できるだけ多くの辺を壊したい。うまく s,…