Submission #1519042
Source Code Expand
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools sys.setrecursionlimit(10**7) inf = 10**20 gosa = 1.0 / 10**10 mod = 10**9 + 7 def LI(): return [int(x) for x in sys.stdin.readline().split()] def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()] def LF(): return [float(x) for x in sys.stdin.readline().split()] def LS(): return sys.stdin.readline().split() def I(): return int(sys.stdin.readline()) def F(): return float(sys.stdin.readline()) def S(): return input() class UnionFind: def __init__(self, size): self.table = [-1 for _ in range(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 return False def subsetall(self): a = [] for i in range(len(self.table)): if self.table[i] < 0: a.append((i, -self.table[i])) return a def main(): n,q = LI() uf = UnionFind(n+2) r = [] for _ in range(q): t,a,b = LI() if t == 0: uf.union(a,b) elif uf.find(a) == uf.find(b): r.append('Yes') else: r.append('No') return '\n'.join(r) print(main())
Submission Info
Submission Time | |
---|---|
Task | B - Union Find |
User | iehn |
Language | Python (3.4.3) |
Score | 100 |
Code Size | 1733 Byte |
Status | AC |
Exec Time | 598 ms |
Memory | 8732 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
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 | 40 ms | 5456 KB |
subtask_01_01.txt | AC | 300 ms | 7120 KB |
subtask_01_02.txt | AC | 43 ms | 6352 KB |
subtask_01_03.txt | AC | 411 ms | 7864 KB |
subtask_01_04.txt | AC | 442 ms | 8732 KB |
subtask_01_05.txt | AC | 67 ms | 5584 KB |
subtask_01_06.txt | AC | 74 ms | 6420 KB |
subtask_01_07.txt | AC | 427 ms | 7692 KB |
subtask_01_08.txt | AC | 472 ms | 8720 KB |
subtask_01_09.txt | AC | 40 ms | 5460 KB |
subtask_01_10.txt | AC | 43 ms | 6352 KB |
subtask_01_11.txt | AC | 420 ms | 7736 KB |
subtask_01_12.txt | AC | 458 ms | 8720 KB |
subtask_01_13.txt | AC | 358 ms | 7508 KB |
subtask_01_14.txt | AC | 45 ms | 6360 KB |
subtask_01_15.txt | AC | 443 ms | 7744 KB |
subtask_01_16.txt | AC | 471 ms | 8728 KB |
subtask_01_17.txt | AC | 598 ms | 7320 KB |
subtask_01_18.txt | AC | 591 ms | 7316 KB |