結果
| 問題 |
No.3200 Sinking Islands
|
| ユーザー |
👑  Kazun
|
| 提出日時 | 2025-07-11 22:45:30 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 470 ms / 2,000 ms |
| コード長 | 6,588 bytes |
| コンパイル時間 | 513 ms |
| コンパイル使用メモリ | 82,104 KB |
| 実行使用メモリ | 106,220 KB |
| 最終ジャッジ日時 | 2025-07-11 22:45:42 |
| 合計ジャッジ時間 | 9,652 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 20 |
ソースコード
class Union_Find:
__slots__ = ("__n", "parents", "rank", "edges", "__group_number")
def __init__(self, N: int) -> None:
""" 0, 1, ..., (N - 1) を要素に持つ Union Find を生成する.
Args:
N (int): 要素数
"""
self.__n = N
self.parents=[-1]*N
self.rank=[0]*N
self.edges=[0]*N
self.__group_number = N
def add_vertex(self) -> int:
""" 頂点を 1 個追加する.
Returns:
int: 追加された頂点の番号
"""
self.__n += 1
self.parents.append(-1)
self.rank.append(0)
self.edges.append(0)
self.__group_number += 1
return self.__n - 1
def add_vertices(self, k: int = 1) -> list[int]:
""" 頂点を k 個追加する.
Args:
k (int, optional): 追加する頂点の個数. Defaults to 1.
Returns:
list[int]: 追加された頂点の番号からなる k 要素のリスト
"""
return [self.add_vertex() for _ in range(k)]
def find(self, x: int) -> int:
""" 要素 x が属している族を調べる
Args:
x (int): 要素
Returns:
int: x が属している族
"""
a=x
while self.parents[a]>=0:
a=self.parents[a]
while self.parents[x]>=0:
y=self.parents[x]
self.parents[x]=a
x=y
return a
def union(self, x: int, y: int, force : bool = False) -> bool:
""" 要素 x と 要素 y を同一視する.
Args:
x (int): 要素 x
y (int): 要素 y
force (bool, optional): True の場合, 必ず x が代表元になるようにマージする. Defaults to False.
Returns:
bool: 元々非連結ならば True, 元々連結ならば False.
"""
x=self.find(x)
y=self.find(y)
if x==y:
self.edges[x]+=1
return False
if (not force) and (self.rank[x] < self.rank[y]):
x,y=y,x
self.__group_number-=1
self.edges[x]+=self.edges[y]+1
self.edges[y]=0
self.parents[x]+=self.parents[y]
self.parents[y]=x
if self.rank[x]==self.rank[y]:
self.rank[x]+=1
return True
def size(self, x: int) -> int:
""" 要素 x が属している族のサイズを求める
Args:
x (int): 要素
Returns:
int: 要素 x が属している族のサイズ
"""
return -self.parents[self.find(x)]
def same(self, x: int, y: int) -> int:
""" 要素 x, y は同一視されているか?
Args:
x (int): 要素
y (int): 要素
Returns:
int: x, y が同一視されていれば True, そうでなければ False
"""
return self.find(x) == self.find(y)
def members(self, x: int) -> list[int]:
""" 要素 x と同一視されている要素のリスト
Args:
x (int): 要素
Returns:
list[int]: 要素 x と同一視されている要素のリスト
"""
root = self.find(x)
return [i for i in range(self.N) if self.find(i) == root]
def edge_count(self, x: int) -> int:
""" 要素 x が属している族における辺の数を求める.
Args:
x (int): 要素
Returns:
int: 要素 x が属している族における辺の数を求める
"""
return self.edges[self.find(x)]
def is_tree(self, x: int) -> bool:
""" 要素 x が属する族が木かどうかを判定する.
Args:
x (int): 要素
Returns:
bool: 木ならば True, そうでなければ False
"""
return self.size(x)==self.edges[self.find(x)]+1
def tree_count(self) -> int:
""" 木になっている族の数を計上する
Returns:
int: 木になっている族の数
"""
return sum(self.is_tree(g) for g in self.representative())
def representative(self) -> list[int]:
""" 代表元のリスト
Returns:
list[int]: 代表元のリスト
"""
return [i for i, x in enumerate(self.parents) if x < 0]
@property
def N(self):
return self.__n
@property
def group_number(self) -> int:
""" 族の個数
Returns:
int: 族の個数
"""
return self.__group_number
def all_group_members(self) -> dict[int, list[int]]:
""" 全ての族の出力
"""
X={r:[] for r in self.representative()}
for k in range(self.N):
X[self.find(k)].append(k)
return X
def group_list(self) -> list[int]:
""" 各要素が属している族のリストを出力する.
"""
return [self.find(x) for x in range(self.N)]
def refresh(self) -> None:
for i in range(self.N):
self.find(i)
def __str__(self) -> str:
return str(list(self.all_group_members().values()))[1: -1]
def __repr__(self) -> str:
return f"{self.__class__.__name__}({self.N})"
def __getitem__(self, index: int) -> int:
return self.find(index)
def __setitem__(self, x: int, y: int) -> None:
self.union(x, y)
#==================================================
def solve():
N, M = map(int, input().split())
edges = [None] * (M + 1)
for j in range(1, M + 1):
u, v = map(int, input().split())
edges[j] = (u, v)
Q = int(input())
query = [0] * Q
collapse = [False] * (M + 1)
for q in range(Q):
query[q] = int(input())
collapse[query[q]] = True
U = Union_Find(N + 1)
for j in range(1, M + 1):
if not collapse[j]:
u, v = edges[j]
U.union(u, v)
ans = [0] * (Q + 1)
for g in U.representative():
if g == 0:
continue
ans[-1] += U.size(g) * (N - U.size(g))
ans[-1] //= 2
for q in range(Q - 1, -1, -1):
ans[q] = ans[q + 1]
u, v = edges[query[q]]
if U.same(u, v):
continue
a = U.size(u)
b = U.size(v)
ans[q] -= a * b
U.union(u, v)
return ans[1:]
#==================================================
import sys
input = sys.stdin.readline
write = sys.stdout.write
write("\n".join(map(str, solve())))