結果

問題 No.3200 Sinking Islands
コンテスト
ユーザー 三価スニウム
提出日時 2025-07-11 23:13:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 614 ms / 2,000 ms
コード長 1,659 bytes
コンパイル時間 375 ms
コンパイル使用メモリ 81,420 KB
実行使用メモリ 120,776 KB
最終ジャッジ日時 2025-07-11 23:14:06
合計ジャッジ時間 11,630 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline().strip()

class Node:
    __slots__ = ('parent', 'size')
    def __init__(self):
        self.parent = None
        self.size = 1

def find(x: Node) -> Node:
    path = []
    while x.parent:
        path.append(x)
        x = x.parent
    result = x
    for x in path:
        x.parent = result
    return result

def union(x: Node, y: Node) -> None:
    px = find(x)
    py = find(y)
    if px is py:
        return
    if px.size > py.size:
        py.parent = px
        px.size += py.size
    else:
        px.parent = py
        py.size += px.size

def main():
    N, M = map(int, input().split())
    edge: list[tuple[int, int]] = []
    for _ in range(M):
        u, v = map(int, input().split())
        edge.append((u-1, v-1))
    
    edgeset = set(range(M))
    B = []
    Q = int(input())
    for _ in range(Q):
        i = int(input())
        B.append(i-1)
        edgeset -= {i-1}
    
    node = [Node() for _ in range(N)]
    ans = [0] * Q
    for i in edgeset:
        if find(node[edge[i][0]]) is not find(node[edge[i][1]]):
            ans[Q-1] += find(node[edge[i][0]]).size * find(node[edge[i][1]]).size
            union(node[edge[i][0]], node[edge[i][1]])
    
    for i, j in enumerate(reversed(B[1:]), start=2):
        ans[Q-i] = ans[Q-i+1]
        if find(node[edge[j][0]]) is not find(node[edge[j][1]]):
            ans[Q-i] += find(node[edge[j][0]]).size * find(node[edge[j][1]]).size
            union(node[edge[j][0]], node[edge[j][1]])
    
    for i in range(Q):
        print((N-1) * N // 2 - ans[i])

if __name__ == '__main__':
    main()
0