結果
問題 | No.2290 UnUnion Find |
ユーザー | NP |
提出日時 | 2024-07-04 21:37:04 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,852 bytes |
コンパイル時間 | 217 ms |
コンパイル使用メモリ | 82,032 KB |
実行使用メモリ | 147,956 KB |
最終ジャッジ日時 | 2024-07-04 21:37:11 |
合計ジャッジ時間 | 5,335 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
59,040 KB |
testcase_01 | AC | 38 ms
52,480 KB |
testcase_02 | AC | 462 ms
125,732 KB |
testcase_03 | TLE | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
testcase_45 | -- | - |
testcase_46 | -- | - |
ソースコード
class DSU:def __init__(self, n):self.parent = list(range(n))self.rank = [1] * ndef find(self, x):if self.parent[x] != x:self.parent[x] = self.find(self.parent[x])return self.parent[x]def union(self, x, y):rootX = self.find(x)rootY = self.find(y)if rootX != rootY:if self.rank[rootX] > self.rank[rootY]:self.parent[rootY] = rootXelif self.rank[rootX] < self.rank[rootY]:self.parent[rootX] = rootYelse:self.parent[rootY] = rootXself.rank[rootX] += 1def process_queries(N, Q, queries):dsu = DSU(N)connected = [set() for _ in range(N)]results = []for query in queries:if query[0] == 1:u = query[1] - 1v = query[2] - 1dsu.union(u, v)connected[u].add(v)connected[v].add(u)elif query[0] == 2:v = query[1] - 1found = Falsefor i in range(N):if i != v and i not in connected[v] and dsu.find(i) != dsu.find(v):results.append(str(i + 1))found = Truebreakif not found:results.append('-1')return "\n".join(results)import sysinput = sys.stdin.readdata = input().split()N = int(data[0])Q = int(data[1])queries = []index = 2for _ in range(Q):query_type = int(data[index])if query_type == 1:u = int(data[index + 1])v = int(data[index + 2])queries.append([1, u, v])index += 3elif query_type == 2:v = int(data[index + 1])queries.append([2, v])index += 2print(process_queries(N, Q, queries))