結果
問題 | No.416 旅行会社 |
ユーザー | roaris |
提出日時 | 2020-12-09 19:38:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,731 ms / 4,000 ms |
コード長 | 1,964 bytes |
コンパイル時間 | 466 ms |
コンパイル使用メモリ | 86,616 KB |
実行使用メモリ | 137,040 KB |
最終ジャッジ日時 | 2023-08-21 10:40:19 |
合計ジャッジ時間 | 16,957 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 343 ms
113,144 KB |
testcase_01 | AC | 73 ms
71,088 KB |
testcase_02 | AC | 71 ms
70,796 KB |
testcase_03 | AC | 74 ms
71,236 KB |
testcase_04 | AC | 72 ms
71,144 KB |
testcase_05 | AC | 75 ms
71,224 KB |
testcase_06 | AC | 75 ms
71,140 KB |
testcase_07 | AC | 89 ms
75,688 KB |
testcase_08 | AC | 159 ms
78,376 KB |
testcase_09 | AC | 293 ms
83,096 KB |
testcase_10 | AC | 552 ms
113,320 KB |
testcase_11 | AC | 527 ms
111,376 KB |
testcase_12 | AC | 558 ms
113,480 KB |
testcase_13 | AC | 308 ms
111,468 KB |
testcase_14 | AC | 1,723 ms
137,040 KB |
testcase_15 | AC | 1,703 ms
135,916 KB |
testcase_16 | AC | 1,655 ms
134,648 KB |
testcase_17 | AC | 1,731 ms
136,744 KB |
testcase_18 | AC | 1,691 ms
136,320 KB |
testcase_19 | AC | 1,272 ms
122,128 KB |
testcase_20 | AC | 1,244 ms
121,628 KB |
ソースコード
import sys input = sys.stdin.readline class Unionfind: def __init__(self, n): self.par = [-1]*n self.rank = [1]*n self.belong = [[v] for v in range(n)] def root(self, x): r = x while not self.par[r]<0: r = self.par[r] t = x while t!=r: tmp = t t = self.par[t] self.par[tmp] = r return r def unite(self, x, y): rx = self.root(x) ry = self.root(y) if rx==ry: return if self.rank[rx]<=self.rank[ry]: self.par[ry] += self.par[rx] self.par[rx] = ry if self.rank[rx]==self.rank[ry]: self.rank[ry] += 1 for v in self.belong[rx]: self.belong[ry].append(v) else: self.par[rx] += self.par[ry] self.par[ry] = rx for v in self.belong[ry]: self.belong[rx].append(v) def is_same(self, x, y): return self.root(x)==self.root(y) def count(self, x): return -self.par[self.root(x)] N, M, Q = map(int, input().split()) AB = [tuple(map(int, input().split())) for _ in range(M)] CD = [tuple(map(int, input().split())) for _ in range(Q)] AB.sort() CD_ = CD[:] CD_.sort() idx = 0 uf = Unionfind(N) for A, B in AB: if idx<Q and (A, B)==CD_[idx]: idx += 1 else: uf.unite(A-1, B-1) ans = [0]*N for v in uf.belong[uf.root(0)]: ans[v] = -1 for i in range(Q-1, -1, -1): C, D = CD[i] if uf.is_same(0, C-1) and not uf.is_same(0, D-1): for v in uf.belong[uf.root(D-1)]: ans[v] = i+1 elif uf.is_same(0, D-1) and not uf.is_same(0, C-1): for v in uf.belong[uf.root(C-1)]: ans[v] = i+1 uf.unite(C-1, D-1) for ans_i in ans[1:]: print(ans_i)