結果

問題 No.3200 Sinking Islands
コンテスト
ユーザー Yakumo221
提出日時 2025-07-12 02:00:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 560 ms / 2,000 ms
コード長 1,660 bytes
コンパイル時間 243 ms
コンパイル使用メモリ 82,420 KB
実行使用メモリ 96,052 KB
最終ジャッジ日時 2025-07-12 02:00:29
合計ジャッジ時間 11,779 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 1-indexed

class UnionFind:
    def __init__(self, n):
        self.table = [-1] * (n+1)

    def root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self.root(x) == self.root(y)
    

    def unite(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return False
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1
        return True

    def get_size(self, x):
        return -self.table[self.root(x)]
    


n,m = map(int, input().split())
uv = []
for i in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    uv.append((u,v))

q = int(input())
blist = [int(input()) - 1 for i in range(q)]

ans = [n*(n-1)//2 for i in range(q+1)]

uf = UnionFind(n)

can = [1 for i in range(m)]

for b in blist:
    can[b] = 0

cnt = 0

for i in range(m):
    if can[i] == 0:
        continue
    u,v = uv[i]
    if uf.find(u,v):
        continue

    usize = uf.get_size(u)
    vsize = uf.get_size(v)
    cnt += usize * vsize

    uf.unite(u,v)

ans[q] -= cnt

for qi in range(q)[::-1]:
    b = blist[qi]
    u,v = uv[b]
    if uf.find(u,v):
        ans[qi] -= cnt
        continue

    usize = uf.get_size(u)
    vsize = uf.get_size(v)
    cnt += usize * vsize

    uf.unite(u,v)

    ans[qi] -= cnt

for i in range(1, q+1):
    print(ans[i])
0