結果
問題 |
No.3200 Sinking Islands
|
ユーザー |
![]() |
提出日時 | 2025-07-11 21:46:38 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 744 ms / 2,000 ms |
コード長 | 1,528 bytes |
コンパイル時間 | 961 ms |
コンパイル使用メモリ | 82,584 KB |
実行使用メモリ | 138,368 KB |
最終ジャッジ日時 | 2025-07-11 21:46:56 |
合計ジャッジ時間 | 14,685 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
from math import comb class UnionFind: def __init__(self,n): self.n = n self.parent_size = [-1]*n def leader(self,a): if self.parent_size[a] < 0: return a self.parent_size[a] = self.leader(self.parent_size[a]) return self.parent_size[a] def merge(self,a,b): x, y = self.leader(a), self.leader(b) if x == y: return if abs(self.parent_size[x]) < abs(self.parent_size[y]): x, y = y, x self.parent_size[x] += self.parent_size[y] self.parent_size[y] = x return def same(self,a,b): return self.leader(a) == self.leader(b) def size(self,a): return abs(self.parent_size[self.leader(a)]) def groups(self): result = [[] for _ in range(self.n)] for i in range(self.n): result[self.leader(i)].append(i) return [r for r in result if r != []] N, M = map(int, input().split()) edge = [list(map(int, input().split())) for _ in range(M)] Q = int(input()) query = [int(input()) for _ in range(Q)] S = set(query) UF = UnionFind(N) SUM = comb(N, 2) for i, (u, v) in enumerate(edge): u, v = u-1, v-1 if i+1 not in S and not UF.same(u, v): SUM -= UF.size(u)*UF.size(v) UF.merge(u, v) ans = [SUM] for i in reversed(range(1, Q)): u, v = edge[query[i]-1] u, v = u-1, v-1 if not UF.same(u, v): SUM -= UF.size(u)*UF.size(v) UF.merge(u, v) ans.append(SUM) print(*ans[::-1], sep="\n")