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

Submission #7469261

Source Code Expand

Copy
```import sys
def input():

N, Q = list(map(int, input().split()))

class Union_Find():
def __init__(self, n):
self.union = [i for i in range(n)]
self.level = [0 for i in range(n)]

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

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

UF = Union_Find(N)

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

else:
if UF.root(A) == UF.root(B):
print("Yes")
else:
print("No")```

#### Submission Info

Submission Time 2019-09-12 04:57:15+0900 B - Union Find Awaful PyPy3 (2.4.0) 100 1079 Byte AC 606 ms 60464 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 167 ms 38256 KB