結果
問題 | No.2290 UnUnion Find |
ユーザー | Akari |
提出日時 | 2023-05-05 21:48:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 353 ms / 2,000 ms |
コード長 | 1,258 bytes |
コンパイル時間 | 528 ms |
コンパイル使用メモリ | 87,168 KB |
実行使用メモリ | 109,920 KB |
最終ジャッジ日時 | 2023-08-15 03:39:32 |
合計ジャッジ時間 | 19,799 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 74 ms
71,332 KB |
testcase_01 | AC | 75 ms
71,608 KB |
testcase_02 | AC | 234 ms
89,004 KB |
testcase_03 | AC | 266 ms
92,228 KB |
testcase_04 | AC | 275 ms
92,252 KB |
testcase_05 | AC | 268 ms
92,188 KB |
testcase_06 | AC | 269 ms
91,996 KB |
testcase_07 | AC | 268 ms
91,856 KB |
testcase_08 | AC | 276 ms
91,876 KB |
testcase_09 | AC | 270 ms
92,048 KB |
testcase_10 | AC | 275 ms
92,180 KB |
testcase_11 | AC | 271 ms
92,068 KB |
testcase_12 | AC | 268 ms
92,016 KB |
testcase_13 | AC | 271 ms
91,864 KB |
testcase_14 | AC | 278 ms
91,896 KB |
testcase_15 | AC | 285 ms
92,012 KB |
testcase_16 | AC | 283 ms
92,080 KB |
testcase_17 | AC | 281 ms
92,076 KB |
testcase_18 | AC | 272 ms
92,180 KB |
testcase_19 | AC | 339 ms
94,508 KB |
testcase_20 | AC | 342 ms
109,920 KB |
testcase_21 | AC | 275 ms
91,072 KB |
testcase_22 | AC | 293 ms
93,128 KB |
testcase_23 | AC | 295 ms
92,324 KB |
testcase_24 | AC | 345 ms
101,092 KB |
testcase_25 | AC | 284 ms
91,396 KB |
testcase_26 | AC | 353 ms
106,496 KB |
testcase_27 | AC | 343 ms
101,380 KB |
testcase_28 | AC | 321 ms
90,652 KB |
testcase_29 | AC | 351 ms
98,524 KB |
testcase_30 | AC | 268 ms
91,356 KB |
testcase_31 | AC | 335 ms
96,156 KB |
testcase_32 | AC | 283 ms
91,476 KB |
testcase_33 | AC | 313 ms
90,672 KB |
testcase_34 | AC | 348 ms
109,856 KB |
testcase_35 | AC | 343 ms
104,360 KB |
testcase_36 | AC | 298 ms
92,064 KB |
testcase_37 | AC | 312 ms
91,772 KB |
testcase_38 | AC | 288 ms
92,416 KB |
testcase_39 | AC | 305 ms
91,284 KB |
testcase_40 | AC | 343 ms
101,408 KB |
testcase_41 | AC | 284 ms
92,920 KB |
testcase_42 | AC | 337 ms
94,012 KB |
testcase_43 | AC | 331 ms
92,452 KB |
testcase_44 | AC | 262 ms
92,088 KB |
testcase_45 | AC | 252 ms
92,336 KB |
testcase_46 | AC | 274 ms
92,328 KB |
ソースコード
import sys def main(): input = sys.stdin.readline n, q = map(int, input().split()) uf = [-1] * n leaders = set(range(n)) def find(x): nonlocal uf y = x while uf[x] >= 0: x = uf[x] while uf[y] >= 0: z = uf[y] uf[y] = x y = z return x def union(x, y): nonlocal uf, leaders x, y = find(x), find(y) if x == y: return False if uf[x] > uf[y]: x, y = y, x uf[x] += uf[y] uf[y] = x leaders.remove(y) return True ans = [] tmp = None for i in range(q): t, *x = map(int, input().split()) if t == 1: a, b = x union(a - 1, b - 1) else: a = x[0] - 1 a = find(a) if len(leaders) == 1: ans.append(-1) else: b = leaders.pop() if b == a: tmp = b b = leaders.pop() ans.append(b + 1) leaders.add(b) if tmp is not None: leaders.add(tmp) tmp = None print('\n'.join(map(str, ans))) if __name__ == '__main__': main()