Submission #10767909


Source Code Expand

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same_check(self, x, y):
        return self.find(x) == self.find(y)

N, Q = map(int, input().split())
uf = UnionFind(N)
for _ in range(Q):
    P, A, B = map(int, input().split())
    if P == 0:
        uf.union(A, B)
        continue
    if uf.find(A) == uf.find(B):
        print('Yes')
    else:
        print('No')

Submission Info

Submission Time
Task B - Union Find
User otomikesuy
Language Python (3.4.3)
Score 100
Code Size 917 Byte
Status AC
Exec Time 1730 ms
Memory 8488 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 1038 ms 3828 KB
subtask_01_02.txt AC 25 ms 7832 KB
subtask_01_03.txt AC 1660 ms 3828 KB
subtask_01_04.txt AC 1681 ms 8488 KB
subtask_01_05.txt AC 123 ms 3064 KB
subtask_01_06.txt AC 123 ms 7856 KB
subtask_01_07.txt AC 1676 ms 3700 KB
subtask_01_08.txt AC 1703 ms 8464 KB
subtask_01_09.txt AC 18 ms 3064 KB
subtask_01_10.txt AC 25 ms 7804 KB
subtask_01_11.txt AC 1670 ms 3700 KB
subtask_01_12.txt AC 1730 ms 8368 KB
subtask_01_13.txt AC 1340 ms 3572 KB
subtask_01_14.txt AC 28 ms 7856 KB
subtask_01_15.txt AC 1673 ms 3700 KB
subtask_01_16.txt AC 1728 ms 8368 KB
subtask_01_17.txt AC 1394 ms 7856 KB
subtask_01_18.txt AC 1365 ms 7856 KB