Submission #421397


Source Code Expand

class UnionFind(object):
 
    def __init__(self, size):
        self.table = [-1 for _ in xrange(size)]
 
    def find(self, x):
        if self.table[x] < 0:
            return x
        self.table[x] = self.find(self.table[x])
        return self.table[x]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 == s2:
            return False
        if self.table[s1] > self.table[s2]:
            s1, s2 = s2, s1
        self.table[s1] += self.table[s2]
        self.table[s2] = s1
        return True
 
N, Q = map(int, raw_input().split())
uf = UnionFind(N+1)
for _ in xrange(Q):
    P, A, B = map(int, raw_input().split())
    if P == 0:
        uf.union(A, B)
    else:
        print "Yes" if uf.same(A, B) else "No"

Submission Info

Submission Time
Task B - Union Find
User puyopop
Language Python (2.7.3)
Score 100
Code Size 870 Byte
Status AC
Exec Time 1763 ms
Memory 4332 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 75 ms 3384 KB
subtask_01_01.txt AC 967 ms 3444 KB
subtask_01_02.txt AC 67 ms 4244 KB
subtask_01_03.txt AC 1471 ms 3448 KB
subtask_01_04.txt AC 1538 ms 4248 KB
subtask_01_05.txt AC 164 ms 3444 KB
subtask_01_06.txt AC 182 ms 4244 KB
subtask_01_07.txt AC 1577 ms 3444 KB
subtask_01_08.txt AC 1577 ms 4240 KB
subtask_01_09.txt AC 58 ms 3440 KB
subtask_01_10.txt AC 67 ms 4244 KB
subtask_01_11.txt AC 1438 ms 3448 KB
subtask_01_12.txt AC 1580 ms 4312 KB
subtask_01_13.txt AC 1266 ms 3440 KB
subtask_01_14.txt AC 72 ms 4240 KB
subtask_01_15.txt AC 1543 ms 3444 KB
subtask_01_16.txt AC 1584 ms 4248 KB
subtask_01_17.txt AC 1756 ms 4248 KB
subtask_01_18.txt AC 1763 ms 4332 KB