結果
問題 |
No.3200 Sinking Islands
|
ユーザー |
![]() |
提出日時 | 2025-07-11 22:01:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 524 ms / 2,000 ms |
コード長 | 4,330 bytes |
コンパイル時間 | 1,328 ms |
コンパイル使用メモリ | 81,648 KB |
実行使用メモリ | 128,956 KB |
最終ジャッジ日時 | 2025-07-11 22:01:26 |
合計ジャッジ時間 | 10,525 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
import sys, math sys.setrecursionlimit(10**8) sys.set_int_max_str_digits(0) INF = 10**18 MOD = 998244353 from bisect import bisect_left, bisect_right from collections import deque, defaultdict, Counter from itertools import product, combinations, permutations, groupby, accumulate from heapq import heapify, heappop, heappush def I(): return sys.stdin.readline().rstrip() def II(): return int(sys.stdin.readline().rstrip()) def IS(): return sys.stdin.readline().rstrip().split() def MII(): return map(int, sys.stdin.readline().rstrip().split()) def LI(): return list(sys.stdin.readline().rstrip()) def TII(): return tuple(map(int, sys.stdin.readline().rstrip().split())) def LII(): return list(map(int, sys.stdin.readline().rstrip().split())) def LSI(): return list(map(str, sys.stdin.readline().rstrip().split())) def GMI(): return list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split())) def kiriage(a, b): return (a+b-1)//b class UnionFind(): def __init__(self, n): self.n = n self.parents = [-1] * n self.link = [i for i in range(n)] #self.L = list(range(n)) #self.R = list(range(n)) self.score = [0] * n def find(self, x): if self.parents[x] < 0: return x else: self.parents[x] = self.find(self.parents[x]) return self.parents[x] def union(self, x, y): rootx = self.find(x) rooty = self.find(y) if rootx == rooty: # すでに same ならなにもしない! return if self.parents[rootx] > self.parents[rooty]: # -3 > -4 のようなケース(前者の方が軍勢が少ない) rootx, rooty = rooty, rootx # rootx = 多い, rooty = 少ない の順番に変更 # 統合(rootx が新しい棟梁, rooty は軍門に下った) self.parents[rootx] += self.parents[rooty] # 多い方(rootx)に併合する self.parents[rooty] = rootx self.link[x], self.link[y] = self.link[y], self.link[x] #self.L[rootx] = min(self.L[rootx], self.L[rooty]) #self.R[rootx] = max(self.R[rootx], self.R[rooty]) self.score[rootx] += self.score[rooty] self.score[rooty] = 0 def size(self, x): # O(1) return -self.parents[self.find(x)] def same(self, x, y): # O(1) return self.find(x) == self.find(y) def members(self, x): # O(K: 集合の要素数) 最小で1、最大でN res = [x] now = self.link[x] while now != x: res.append(now) now = self.link[now] return res #def get_LR(self, x): #x = self.find(x) #return (self.L[x], self.R[x]) def roots(self): # O(N) return [i for i, x in enumerate(self.parents) if x < 0] def group_count(self): # roots() の呼び出しは全頂点の par をチェックする=遅いため、N回使うと TLE する return len(self.roots()) def all_group_members(self): group_members = defaultdict(list) for member in range(self.n): group_members[self.find(member)].append(member) return group_members N, M = MII() edges = [] for i in range(M): u, v = MII() u -= 1 v -= 1 edges.append((u, v)) Q = II() query = [] for i in range(Q): b = II() b -= 1 query.append(b) query_set = set(query) uf = UnionFind(N) # query に含まれる辺以外を結ぶ connected_pairs = 0 for i in range(M): u, v = edges[i] if i not in query_set: # 結ぶ # 連結か? if uf.same(u, v): # もともと連結だったら何もしない pass else: # u の軍勢数 # v の軍勢数 zobun = uf.size(u) * uf.size(v) connected_pairs += zobun uf.union(u, v) total = N*(N - 1)//2 # この時点での答えは? ansl = [total - connected_pairs] for i in range(Q - 1): target_edge_id = query[-1 - i] u, v = edges[target_edge_id] if uf.same(u, v): # もともと連結だったら何もしない pass else: # u の軍勢数 # v の軍勢数 zobun = uf.size(u) * uf.size(v) connected_pairs += zobun uf.union(u, v) ansl.append(total - connected_pairs) ansl.reverse() print(*ansl, sep='\n')