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

pekempeyのブログ

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

Codeforces Round #395 (Div. 1) E. Timofey and our friends animals

snuke さんの以下の記事を読んでいればやるだけ?

snuke.hatenablog.com

http://codeforces.com/contest/763/problem/E

問題概要

n 頂点のグラフが与えられる。頂点番号が[l,r]であるものだけを取り出したとき、連結成分がいくつあるか、というクエリが Q 個与えられるので順次処理せよ。

解法

平方分割。k≦5 という条件があるため、各頂点の次数は 10 以下で抑えられる。

あとは snuke さんの平方分割を適用するだけ。undo 可能な union find が作れることは割と自明だろう。経路圧縮は意味を成さないし、定数倍を悪化させるだけなのでやめておこう。

3416 ms。