結果
問題 |
No.3200 Sinking Islands
|
ユーザー |
![]() |
提出日時 | 2025-07-11 21:52:13 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 691 ms / 2,000 ms |
コード長 | 1,130 bytes |
コンパイル時間 | 430 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 133,332 KB |
最終ジャッジ日時 | 2025-07-11 21:52:39 |
合計ジャッジ時間 | 14,064 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
n, m = map(int, input().split()) *p, = range(n) size = [1]*n def root(x): if x == p[x]: return x p[x] = y = root(p[x]) return y def unite(x, y): px = root(x); py = root(y) if px == py: return 0 sx = size[px]; sy = size[py] if sy < sx: p[py] = px size[px] += sy else: p[px] = py size[py] += sx return 1 UV = [tuple(map(int, input().split())) for _ in range(m)] q = int(input()) B = [int(input())-1 for _ in range(q)] Ans = [] B = B[::-1] ans = n * (n-1) // 2 C = set(B) L = [1 for _ in range(n)] for i in range(m): if i in C: continue u, v = UV[i] u, v = u-1, v-1 lu = root(u) lv = root(v) if lu == lv: continue c0 = L[lu] c1 = L[lv] unite(u, v) ln = root(u) ans -= c0 * c1 L[ln] = c0 + c1 for i in B: Ans.append(ans) u, v = UV[i] u, v = u-1, v-1 lu = root(u) lv = root(v) if lu == lv: continue c0 = L[lu] c1 = L[lv] unite(u, v) ln = root(u) ans -= c0 * c1 L[ln] = c0 + c1 Ans = Ans[::-1] for ans in Ans: print(ans)