結果
問題 | No.416 旅行会社 |
ユーザー | rpy3cpp |
提出日時 | 2016-08-26 23:18:44 |
言語 | PyPy3 (7.3.13) |
結果 |
AC
|
実行時間 | 1,138 ms / 4,000 ms |
コード長 | 2,073 bytes |
コンパイル時間 | 1,094 ms |
コンパイル使用メモリ | 87,176 KB |
実行使用メモリ | 160,628 KB |
最終ジャッジ日時 | 2023-08-21 09:41:57 |
合計ジャッジ時間 | 13,385 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 341 ms
136,248 KB |
testcase_01 | AC | 72 ms
71,364 KB |
testcase_02 | AC | 70 ms
71,268 KB |
testcase_03 | AC | 70 ms
71,236 KB |
testcase_04 | AC | 70 ms
71,396 KB |
testcase_05 | AC | 72 ms
71,444 KB |
testcase_06 | AC | 73 ms
71,224 KB |
testcase_07 | AC | 94 ms
75,700 KB |
testcase_08 | AC | 177 ms
80,116 KB |
testcase_09 | AC | 303 ms
84,240 KB |
testcase_10 | AC | 395 ms
134,820 KB |
testcase_11 | AC | 378 ms
134,212 KB |
testcase_12 | AC | 390 ms
134,676 KB |
testcase_13 | AC | 324 ms
136,168 KB |
testcase_14 | AC | 1,050 ms
159,564 KB |
testcase_15 | AC | 1,138 ms
160,628 KB |
testcase_16 | AC | 1,121 ms
160,604 KB |
testcase_17 | AC | 1,135 ms
159,980 KB |
testcase_18 | AC | 1,125 ms
159,392 KB |
testcase_19 | AC | 962 ms
128,960 KB |
testcase_20 | AC | 921 ms
129,288 KB |
ソースコード
class DisjointSet(object): def __init__(self, n): self.parent = list(range(n)) self.rank = [0] * n def union(self, x, y): self._link(self.find_set(x), self.find_set(y)) def _link(self, x, y): if x == y: return if self.rank[x] > self.rank[y]: self.parent[y] = x else: self.parent[x] = y if self.rank[x] == self.rank[y]: self.rank[y] += 1 def find_set(self, x): xp = self.parent[x] if xp != x: self.parent[x] = self.find_set(xp) return self.parent[x] def read_data(): N, M, Q = map(int, input().split()) ABs = [] for m in range(M): a, b = map(int, input().split()) ABs.append((a-1, b-1)) CDs = [] for q in range(Q): c, d = map(int, input().split()) CDs.append((c-1, d-1)) return N, M, Q, ABs, CDs def solve(N, M, Q, ABs, CDs): Es = [set() for i in range(N)] for a, b in ABs: Es[a].add(b) Es[b].add(a) for c, d in CDs: Es[c].remove(d) Es[d].remove(c) ds = DisjointSet(N) for u in range(N): for v in Es[u]: ds.union(u, v) ans = [0] * N ans[0] = -1 update_ans(ans, 0, Es, -1) val = Q for c, d in CDs[::-1]: rc = ds.find_set(c) rd = ds.find_set(d) r0 = ds.find_set(0) if rc != rd: if rc == r0: update_ans(ans, rd, Es, val) elif rd == r0: update_ans(ans, rc, Es, val) ds.union(c, d) Es[c].add(d) Es[d].add(c) val -= 1 return ans def update_ans(ans, root, Es, val): ''' root に連結した頂点 v について、ans[v] = val とする。 ''' que = [root] ans[root] = val while que: u = que.pop() for v in Es[u]: if not ans[v]: ans[v] = val que.append(v) N, M, Q, ABs, CDs = read_data() ans = solve(N, M, Q, ABs, CDs) for k in ans[1:]: print(k)