結果

問題 No.3200 Sinking Islands
コンテスト
ユーザー dp_ijk
提出日時 2025-07-11 21:50:57
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 608 ms / 2,000 ms
コード長 2,360 bytes
コンパイル時間 492 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 108,356 KB
最終ジャッジ日時 2025-07-11 21:51:12
合計ジャッジ時間 13,024 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

class DSU:
   def __init__(self, N: int, *, keep_order: bool = False):
      self.T: list[int] = [-1]*N
      self._num_cc = N
      self._keep_order = keep_order

   def add_node(self):
      self.T.append(-1)
      self._num_cc += 1

   def leader(self, v: int) -> int:
      assert 0 <= v < len(self.T), f"{v=} / N={len(self.T)}"
      r = v
      while self.T[r] >= 0:
         r = self.T[r]
      while v != r:
         self.T[v], v = r, self.T[v]
      return r

   def __getitem__(self, v: int) -> int:
      return self.leader(v)

   def merge(self, a: int, b: int, /) -> bool:
      a, b = self.leader(a), self.leader(b)
      if a == b:
         return False
      if not self._keep_order:
         if -(self.T[a]) < -(self.T[b]):
            a, b = b, a
      self.T[a] += self.T[b]
      self.T[b] = a
      self._num_cc -= 1
      return True

   def same(self, a: int, b: int) -> bool:
      return self.leader(a) == self.leader(b)

   def size(self, a: int) -> int:
      return -(self.T[self.leader(a)])

   def groups(self) -> list[list[int]]:
      N = self.num_nodes()
      res = [[] for _ in range(N)]
      for v in range(N):
         res[self.leader(v)].append(v)
      return [group for group in res if len(group) > 0]

   def copy(self):
      res = self.__class__(0)
      for attr in res.__dict__:
         setattr(res, attr, getattr(self, attr))
      res.T = self.T[:]
      return res

   def num_nodes(self) -> int:
      return len(self.T)

   def num_components(self) -> int:
      return self._num_cc

   def __repr__(self) -> str:
      groups = self.copy().groups()
      return repr(sorted(map(sorted, groups)))




def solve(N, M, Es, Q, B):
   ans = []
   cnt = N*(N-1)//2
   uf = DSU(N)

   def delta(j):
      a, b = Es[j]
      size, size2 = uf.size(a), uf.size(b)
      if uf.same(a, b):
         return 0
      uf.merge(a, b)
      return -(size * size2)

   good = [True]*M
   for b in B:
      good[b] = False
   for j in range(M):
      if good[j]:
         cnt += delta(j)

   for b in reversed(B):
      ans.append(cnt)
      cnt += delta(b)
   return ans[::-1]


N, M = map(int, input().split())
Es = []
for _ in range(M):
   a, b = map(lambda x: int(x) - 1, input().split())
   Es.append((a, b))
Q = int(input())
B = [int(input()) - 1 for _ in range(Q)]

ans = solve(N, M, Es, Q, B)
for a in ans:
   print(a)
0