結果
問題 | No.416 旅行会社 |
ユーザー | tktk_snsn |
提出日時 | 2020-12-14 17:10:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,428 ms / 4,000 ms |
コード長 | 1,044 bytes |
コンパイル時間 | 825 ms |
コンパイル使用メモリ | 86,776 KB |
実行使用メモリ | 153,040 KB |
最終ジャッジ日時 | 2023-08-21 10:43:31 |
合計ジャッジ時間 | 16,369 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 371 ms
114,028 KB |
testcase_01 | AC | 94 ms
71,328 KB |
testcase_02 | AC | 94 ms
71,420 KB |
testcase_03 | AC | 94 ms
71,760 KB |
testcase_04 | AC | 96 ms
71,516 KB |
testcase_05 | AC | 97 ms
71,700 KB |
testcase_06 | AC | 102 ms
72,104 KB |
testcase_07 | AC | 119 ms
76,660 KB |
testcase_08 | AC | 190 ms
79,088 KB |
testcase_09 | AC | 303 ms
83,624 KB |
testcase_10 | AC | 578 ms
114,108 KB |
testcase_11 | AC | 587 ms
119,544 KB |
testcase_12 | AC | 618 ms
123,036 KB |
testcase_13 | AC | 366 ms
119,944 KB |
testcase_14 | AC | 1,380 ms
149,684 KB |
testcase_15 | AC | 1,428 ms
152,520 KB |
testcase_16 | AC | 1,422 ms
153,040 KB |
testcase_17 | AC | 1,414 ms
149,148 KB |
testcase_18 | AC | 1,378 ms
150,128 KB |
testcase_19 | AC | 1,142 ms
134,584 KB |
testcase_20 | AC | 1,116 ms
133,168 KB |
ソースコード
from collections import defaultdict N, M, Q = map(int, input().split()) bridge = defaultdict(int) for _ in range(M): a, b = map(int, input().split()) bridge[(a, b)] = Q + 1 for i in range(1, Q + 1): c, d = map(int, input().split()) bridge[(c, d)] = i data = [[i] for i in range(N)] ans = [0] * N def find(x): if isinstance(data[x], list): return x data[x] = find(data[x]) return data[x] def merge(x, y, time): x = find(x) y = find(y) if x == y: return if x > y: x, y = y, x if x == 0: while data[y]: i = data[y].pop() ans[i] = time data[x].append(i) data[y] = 0 return if len(data[x]) > len(data[y]): x, y = y, x while data[x]: data[y].append(data[x].pop()) data[x] = y query = [(n, a, b) for (a, b), n in bridge.items()] query.sort(reverse=True) for n, a, b in query: merge(a - 1, b - 1, n) for a in ans[1:]: if a > Q: print(-1) else: print(a)