結果
問題 | No.416 旅行会社 |
ユーザー |
![]() |
提出日時 | 2025-01-12 22:34:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,456 ms / 4,000 ms |
コード長 | 2,681 bytes |
コンパイル時間 | 840 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 186,016 KB |
最終ジャッジ日時 | 2025-01-12 22:34:40 |
合計ジャッジ時間 | 19,077 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
import typingclass DSU:def __init__(self, n: int = 0) -> None:self._n = nself.parent_or_size = [-1] * ndef merge(self, a: int, b: int) -> int:assert 0 <= a < self._nassert 0 <= b < self._nx = self.leader(a)y = self.leader(b)if x == y:return xif -self.parent_or_size[x] < -self.parent_or_size[y]:x, y = y, xself.parent_or_size[x] += self.parent_or_size[y]self.parent_or_size[y] = xreturn xdef same(self, a: int, b: int) -> bool:assert 0 <= a < self._nassert 0 <= b < self._nreturn self.leader(a) == self.leader(b)def leader(self, a: int) -> int:assert 0 <= a < self._nparent = self.parent_or_size[a]while parent >= 0:if self.parent_or_size[parent] < 0:return parentself.parent_or_size[a], a, parent = (self.parent_or_size[parent],self.parent_or_size[parent],self.parent_or_size[self.parent_or_size[parent]])return adef size(self, a: int) -> int:assert 0 <= a < self._nreturn -self.parent_or_size[self.leader(a)]def groups(self) -> typing.List[typing.List[int]]:leader_buf = [self.leader(i) for i in range(self._n)]result: typing.List[typing.List[int]] = [[] for _ in range(self._n)]for i in range(self._n):result[leader_buf[i]].append(i)return list(filter(lambda r: r, result))N, M, Q = map(int, input().split())AB = set([tuple(map(int, input().split())) for _ in range(M)])CD = []dic = {}for i in range(1,N+1):dic[i] = {i}dsu = DSU(N + 1)for i in range(Q):cd = tuple(map(int, input().split()))CD.append(cd)AB.remove(cd)X = [0] * (N + 1)for a,b in AB:al = dsu.leader(a)bl = dsu.leader(b)if al == bl:continuedsu.merge(a,b)if dsu.leader(a) == al:dic[al] |= dic[bl]dic.pop(bl)else:dic[bl] |= dic[al]dic.pop(al)for i in dic[dsu.leader(1)]:X[i] = -1CD = CD[::-1]for i, (c,d) in enumerate(CD):if dsu.same(c,d):continueif dsu.same(1,c):for d in dic[dsu.leader(d)]:X[d]= Q - ielif dsu.same(1,d):for c in dic[dsu.leader(c)]:X[c]= Q - icl = dsu.leader(c)dl = dsu.leader(d)dsu.merge(c, d)if dsu.leader(c) == cl:dic[cl] |= dic[dl]dic.pop(dl)else:dic[dl] |= dic[cl]dic.pop(cl)#print(i,list(dic.items()))for x in X[2:]:print(x)