Submission #6184904


Source Code Expand

class UnionFind:
    def __init__(self, size):
        self.table = [-1]*size
    
    def find(self, x):
        if self.table[x]<0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]
    
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1!=s2:
            if self.table[s1]>=self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        else:
            return False

N, Q = map(int, input().split())
u = UnionFind(N)
for i in range(Q):
    P, A, B = map(int, input().split())
    if P: # 判定クエリ
        ans = "Yes" if u.find(A-1)==u.find(B-1) else 'No'
        print(ans)
    else: # 連結クエリ
        u.union(A-1, B-1)

Submission Info

Submission Time
Task B - Union Find
User takeshiD
Language Python (3.4.3)
Score 100
Code Size 957 Byte
Status AC
Exec Time 1760 ms
Memory 5608 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 3064 KB
subtask_01_01.txt AC 1036 ms 3444 KB
subtask_01_02.txt AC 18 ms 3828 KB
subtask_01_03.txt AC 1660 ms 3828 KB
subtask_01_04.txt AC 1760 ms 4468 KB
subtask_01_05.txt AC 124 ms 3064 KB
subtask_01_06.txt AC 118 ms 3956 KB
subtask_01_07.txt AC 1677 ms 3700 KB
subtask_01_08.txt AC 1651 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 1676 ms 3700 KB
subtask_01_12.txt AC 1688 ms 4468 KB
subtask_01_13.txt AC 1391 ms 3572 KB
subtask_01_14.txt AC 22 ms 3828 KB
subtask_01_15.txt AC 1684 ms 3572 KB
subtask_01_16.txt AC 1745 ms 4468 KB
subtask_01_17.txt AC 1726 ms 5604 KB
subtask_01_18.txt AC 1717 ms 5608 KB