結果
問題 | No.2290 UnUnion Find |
ユーザー | yassu0320 |
提出日時 | 2023-05-06 17:54:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 740 ms / 2,000 ms |
コード長 | 3,282 bytes |
コンパイル時間 | 227 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 116,460 KB |
最終ジャッジ日時 | 2024-05-03 03:41:42 |
合計ジャッジ時間 | 33,548 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 109 ms
79,744 KB |
testcase_01 | AC | 109 ms
79,744 KB |
testcase_02 | AC | 473 ms
92,032 KB |
testcase_03 | AC | 578 ms
97,920 KB |
testcase_04 | AC | 582 ms
97,664 KB |
testcase_05 | AC | 559 ms
97,664 KB |
testcase_06 | AC | 570 ms
97,792 KB |
testcase_07 | AC | 570 ms
98,048 KB |
testcase_08 | AC | 561 ms
97,920 KB |
testcase_09 | AC | 568 ms
97,792 KB |
testcase_10 | AC | 578 ms
97,664 KB |
testcase_11 | AC | 569 ms
97,664 KB |
testcase_12 | AC | 565 ms
97,920 KB |
testcase_13 | AC | 579 ms
97,664 KB |
testcase_14 | AC | 563 ms
97,664 KB |
testcase_15 | AC | 587 ms
97,792 KB |
testcase_16 | AC | 581 ms
97,664 KB |
testcase_17 | AC | 560 ms
97,792 KB |
testcase_18 | AC | 582 ms
97,664 KB |
testcase_19 | AC | 696 ms
99,872 KB |
testcase_20 | AC | 723 ms
116,460 KB |
testcase_21 | AC | 513 ms
92,032 KB |
testcase_22 | AC | 596 ms
93,056 KB |
testcase_23 | AC | 583 ms
93,056 KB |
testcase_24 | AC | 708 ms
106,624 KB |
testcase_25 | AC | 578 ms
91,776 KB |
testcase_26 | AC | 740 ms
112,128 KB |
testcase_27 | AC | 692 ms
107,520 KB |
testcase_28 | AC | 631 ms
96,384 KB |
testcase_29 | AC | 689 ms
103,936 KB |
testcase_30 | AC | 526 ms
91,904 KB |
testcase_31 | AC | 740 ms
102,144 KB |
testcase_32 | AC | 573 ms
92,672 KB |
testcase_33 | AC | 629 ms
96,128 KB |
testcase_34 | AC | 725 ms
115,584 KB |
testcase_35 | AC | 716 ms
109,824 KB |
testcase_36 | AC | 590 ms
92,288 KB |
testcase_37 | AC | 611 ms
95,872 KB |
testcase_38 | AC | 566 ms
92,032 KB |
testcase_39 | AC | 586 ms
92,928 KB |
testcase_40 | AC | 704 ms
107,520 KB |
testcase_41 | AC | 544 ms
91,520 KB |
testcase_42 | AC | 669 ms
99,840 KB |
testcase_43 | AC | 649 ms
99,840 KB |
testcase_44 | AC | 564 ms
98,176 KB |
testcase_45 | AC | 560 ms
97,920 KB |
testcase_46 | AC | 628 ms
97,792 KB |
ソースコード
#!/usr/bin/env pypy3 from pprint import pprint from string import ascii_lowercase as letter from sys import setrecursionlimit, stderr, stdin from typing import Dict, Generic, Iterable, Iterator, List, Optional, Set, TypeVar, Union try: import pypyjit pypyjit.set_param('max_unroll_recursion=-1') except ModuleNotFoundError: ... INF: int = (1 << 62) - 1 MOD1000000007 = 10**9 + 7 MOD998244353 = 998244353 setrecursionlimit(500_000) # 5*10**5 readline = stdin.readline input = lambda: stdin.readline().rstrip('\r\n') def copy2d(a: list) -> list: return [[y for y in x] for x in a] def copy3d(a: list) -> list: return [[[z for z in y] for y in x] for x in a] def flattern2d(mat: list) -> list: return [x for a in mat for x in a] def debug(*a): pprint(a, stream=stderr) def inputs(type_=int, one_word=False) -> list: in_ = input() if one_word: ins = list(in_) else: ins = in_.split() if isinstance(type_, Iterable): return [t(x) for t, x in zip(type_, ins)] else: return list(map(type_, ins)) def input_iter(size, type_: type = int, one_word: bool = False): for _ in range(size): yield inputs(type_=type_, one_word=one_word) def inputi() -> int: return int(readline()) yn = ['no', 'yes'] Yn = ['No', 'Yes'] YN = ['NO', 'YES'] # start coding # {{{ UnionFind class UnionFind: """ Ref: github.com/cheran-senthil/PyRival/blob/master/pyrival/data_structures/DisjointSetUnion.py """ def __init__(self, n): self.parent = list(range(n)) self.n = n self._size = [1] * n self.num_groups = n def find(self, a: int) -> int: acopy = a while a != self.parent[a]: a = self.parent[a] while acopy != a: self.parent[acopy], acopy = a, self.parent[acopy] return a def union(self, a: int, b: int) -> int: a, b = self.find(a), self.find(b) if a == b: return a if self._size[a] < self._size[b]: a, b = b, a self.num_groups -= 1 self.parent[b] = a self._size[a] += self._size[b] return a def same(self, a: int, b: int) -> bool: return self.find(a) == self.find(b) def size(self, a) -> int: return self._size[self.find(a)] def groups(self): """ 計算量: O(n * log(n) * alpha(n)) """ gs = dict() for u in range(self.n): p = self.find(u) if p not in gs: gs[p] = [] gs[p].append(u) return list(gs.values()) def __len__(self): return self.num_groups # }}} n, q = inputs() uf = UnionFind(n) s = set() for u in range(n): s.add(u) for _ in range(q): t, *args = inputs() if t == 1: u, v = args u -= 1 v -= 1 r = uf.find(u) s.discard(r) r = uf.find(v) s.discard(r) r = uf.union(u, v) s.add(r) else: if len(s) == 1: print(-1) continue v, = args v -= 1 r1, r2 = s.pop(), s.pop() if uf.find(v) == r1: print(r2 + 1) else: print(r1 + 1) s.add(r1) s.add(r2)