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

pekempeyのブログ

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

Dynamic connectivity contest: Connect and Disconnect

Dynamic Connectivity

こんなコンテストがあったんですね。

問題ページ

問題概要

  1. 辺の追加
  2. 辺の削除
  3. 連結成分の個数を求める

という 3 種類のクエリが与えられるので順次処理せよ。

解法

オフライン dynamic connectivity。anta さんの wiki を参考にした。

Decomposable searching problem - オフラインの場合 - yukicoder

辺 e の追加タイミングを左端、削除タイミングを右端とした区間を考えると、非遅延セグメント木の要領で dynamic connectivity を実現できる。

undo を実装するには操作履歴を stack に積んでおけばいい。

前作った dynamic connectivity は当然のごとく MLE した。何とかしたいなぁ…。