HHKB プログラミングコンテスト 2022（AtCoder Beginner Contest 235）E - MST + 1 (500) - procon-kirokuyou

HHKB プログラミングコンテスト 2022（AtCoder Beginner Contest 235）E - MST + 1 (500)

毎回最小全域木を作ると明らかに間に合わない

辺とクエリを一緒に見ながらクラスカル法を行う

見ているのが辺の場合、通常通りに処理をする

見ているのがクエリの場合、

辺を追加する場合は代わりに答えにYesを入れる

辺を追加しない場合は答えにNoを入れる

ソートがボトルネックで$ \mathcal{O}((M+Q) \log(M+Q))

問題: https://atcoder.jp/contests/abc235/tasks/abc235_e

提出: https://atcoder.jp/contests/abc235/submissions/28545172

#HHKBプログラミングコンテスト2022 #ABC235 #500pt #E #ABC #AtCoder

#UnionFind #クラスカル法