Contest Duration: ~ (local time) (90 minutes) Back to Home

Submission #7469229

Source Code Expand

Copy
```import sys
def input():

N, Q = list(map(int, input().split()))
union = [i for i in range(N)]
level = [0 for i in range(N)]

def root(union, i, mode=0):
keiro = [i]
ans = i
while ans != union[ans]:
ans = union[ans]
keiro.append(ans)
if mode == 0:
return ans
else:
return ans, keiro

def unite(union, i, j, level):
root_i, list_i = root(union, i, 1)
root_j, list_j = root(union, j, 1)
if root_i != root_j:
if level[root_i] < level[root_j]:
level[root_j] = max(level[root_i] + 1, level[root_j])
for node in list_i:
union[node] = root_j
else:
level[root_i] = max(level[root_j] + 1, level[root_i])
for node in list_j:
union[node] = root_i

for q in range(Q):
P, A, B = list(map(int, input().split()))
A -= 1
B -= 1
if P == 0:
unite(union, A, B, level)

else:
if root(union, A) == root(union, B):
print("Yes")
else:
print("No")```

Submission Info

Submission Time 2019-09-12 04:46:05+0900 B - Union Find Awaful PyPy3 (2.4.0) 100 961 Byte AC 608 ms 64856 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
 AC × 1
 AC × 19
Set Name Test Cases
Sample 00_sample_01.txt
Case Name Status Exec Time Memory
00_sample_01.txt 175 ms 38256 KB