Submission #7010690


Source Code Expand

# Path compression
class UnionFindPathCompression():
    def __init__(self, n):
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        self.parents[y] = x
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
      
N, Q = map(int, input().split())

uf = UnionFindPathCompression(N)

for _ in range(Q):
  p, a, b = map(int, input().split())
  if p:
    print('Yes' if uf.same(a, b) else 'No')
  else:
    uf.union(a, b)

Submission Info

Submission Time
Task B - Union Find
User nkmk
Language Python (3.4.3)
Score 100
Code Size 791 Byte
Status AC
Exec Time 1763 ms
Memory 5596 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
All 00_sample_01.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 17 ms 3192 KB
subtask_01_01.txt AC 1025 ms 3444 KB
subtask_01_02.txt AC 19 ms 3828 KB
subtask_01_03.txt AC 1700 ms 3828 KB
subtask_01_04.txt AC 1709 ms 4468 KB
subtask_01_05.txt AC 122 ms 3064 KB
subtask_01_06.txt AC 115 ms 3956 KB
subtask_01_07.txt AC 1763 ms 3572 KB
subtask_01_08.txt AC 1667 ms 4468 KB
subtask_01_09.txt AC 17 ms 3064 KB
subtask_01_10.txt AC 19 ms 3828 KB
subtask_01_11.txt AC 1734 ms 3700 KB
subtask_01_12.txt AC 1709 ms 4468 KB
subtask_01_13.txt AC 1322 ms 3572 KB
subtask_01_14.txt AC 22 ms 3828 KB
subtask_01_15.txt AC 1674 ms 3572 KB
subtask_01_16.txt AC 1701 ms 4468 KB
subtask_01_17.txt AC 1347 ms 4084 KB
subtask_01_18.txt AC 1638 ms 5596 KB