Atcoder水色精進記録
挑戦していた水色が自力で解けなかったため、未ACの緑
ABC218
E - Destruction
https://atcoder.jp/contests/abc218/tasks/abc218_e
アルゴリズム・データ構造
DP
考察
辺を取り除く最低が規定されていないため、負の辺は取り除く必要なし
取り除いていい辺はできるだけ値が大きい方が良い
→Cの値でsortして小さい順にUnionFindで結合、すでに連結だったらその辺を取り除く
(ただし、Cが0以上の場合)
計算量
事前ソート NlogN
loop数 N
UnionFind ならし：α(N) 最悪：logN
全体 NlogN
提出
感想
UnionFindについて慣れてきた。
緑色の問題はかなりの確率でACできる。(Atcoderの色判定の精度がすごい)