結果

問題 No.3200 Sinking Islands
コンテスト
ユーザー Yakumo221
提出日時 2025-07-12 02:00:15
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 362 ms / 2,000 ms
+ 329µs
コード長 1,660 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 234 ms
コンパイル使用メモリ 95,460 KB
実行使用メモリ 102,488 KB
最終ジャッジ日時 2026-07-13 04:36:41
合計ジャッジ時間 9,481 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# 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