読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Bridge

Dynamic connectivity contest: Bridges: The Final Battle

http://codeforces.com/gym/100551/problem/D 問題概要 辺の追加・削除のクエリが与えられる。クエリを処理する毎に橋の個数を出力せよ。 1≦N,K≦105

Dynamic connectivity contest: GraphAero

問題ページ とりあえず LC 木で解けるので解きました。ただこの方法だと D 問題が解けない。 問題概要 N 頂点 M 辺の無向グラフが与えられる。辺(u,v) を追加するというクエリが K 個与えられるので順次処理せよ。各クエリを処理した後、グラフ中にある橋の…

Dynamic connectivity contest: Bridges in a Tree

問題ページ 問題概要 木が与えられる。初期状態に辺 e1, e2 ,..., eK を加えたとき橋はいくつあるかという M 個のクエリを順次処理せよ。 2≦N≦100,000 1≦M≦100,000 ΣK≦100,000