結果

問題 No.3200 Sinking Islands
ユーザー u_kun
提出日時 2025-08-12 21:41:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 632 ms / 2,000 ms
コード長 2,622 bytes
コンパイル時間 487 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 158,900 KB
最終ジャッジ日時 2025-08-12 21:41:40
合計ジャッジ時間 15,592 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

class UnionFind:
    # N 頂点で初期化
    def __init__(self, N):
        # 木の根 r に対して、self._size[r] は木の頂点数を表す
        # 根でない頂点に対しては不定 (参照しない)
        self._size = [1 for i in range(N)]
        # 頂点 v に対して、self._parent[v] は v の親を表す (v が根なら -1)
        self._parent = [-1 for i in range(N)]

    # 代表値を求める (経路圧縮も行う)
    def find(self, v):
        if self._parent[v] == -1:
            return v
        else:
            vertices = []
            while self._parent[v] >= 0:
                vertices.append(v)
                v = self._parent[v]
            for i in vertices:
                self._parent[i] = v
            return v

    # 2 つの集合を併合する
    # 実際に併合が起こったかどうかを返しておくと便利
    def unite(self, x, y):
        # 代表値 (木の根) を求める
        x = self.find(x)
        y = self.find(y)

        # すでに同じ集合に属するときは何もしない
        if x == y:
            return False

        # 木のサイズが小さいものを大きいものに併合
        if self._size[x] < self._size[y]:
            x, y = y, x
        self._parent[y] = x
        self._size[x] += self._size[y]
        return True

    # 2 つの要素が同じ集合に属するか求める (あると便利)
    def same(self, x, y):
        x = self.find(x)
        y = self.find(y)
        return x == y

    # 集合のサイズを求める (あると便利)
    def size(self, x):
        return self._size[self.find(x)]

N, M = map(int, input().split())
E = []
for e_id in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    E.append((u, v))

Q = int(input())
Q_list = []
for _ in range(Q):
    Q_list.append(int(input()) - 1)

Q_set = set(Q_list)

uf = UnionFind(N)
for e_id in range(M):
    u, v = E[e_id]
    
    if e_id in Q_set:
        continue
    else:
        uf.unite(u, v)

ans = []

tmp = set()
can = 0
for vid in range(N):
    root_vid = uf.find(vid)
    
    if root_vid in tmp:
        continue
    else:
        tmp.add(root_vid)
        n = uf._size[root_vid]
        can += n*(n-1)//2

ans.append((N*(N-1)//2) - can)

Q_list.reverse()

for i in range(Q - 1):
    e_id = Q_list[i]
    
    u, v = E[e_id]
    
    if uf.same(u, v):
        ans.append(ans[-1])
        continue
    
    ans.append(ans[-1] - uf.size(u)*uf.size(v))
    uf.unite(u, v)

ans.reverse()

for elem in ans:
    print(elem)
0