Submission #7469261


Source Code Expand

Copy
import sys
def input():
	return sys.stdin.readline().strip()

N, Q = list(map(int, input().split()))


class Union_Find():
	def __init__(self, n):
		self.union = [i for i in range(n)]
		self.level = [0 for i in range(n)]

	def root(self, i, mode=0):
		keiro = [i]
		ans = i
		while ans != self.union[ans]:
			ans = self.union[ans]
			keiro.append(ans)
		if mode == 0:
			return ans
		else:
			return ans, keiro

	def unite(self, i, j):
		root_i, list_i = self.root(i, 1)
		root_j, list_j = self.root(j, 1)
		if root_i != root_j:
			if self.level[root_i] < self.level[root_j]:
				self.level[root_j] = max(self.level[root_i] + 1, self.level[root_j])
				for node in list_i:
					self.union[node] = root_j
			else:
				self.level[root_i] = max(self.level[root_j] + 1, self.level[root_i])
				for node in list_j:
					self.union[node] = root_i

UF = Union_Find(N)

for q in range(Q):
	P, A, B = list(map(int, input().split()))
	if P == 0:
		UF.unite(A, B)

	else:
		if UF.root(A) == UF.root(B):
			print("Yes")
		else:
			print("No")

Submission Info

Submission Time
Task B - Union Find
User Awaful
Language PyPy3 (2.4.0)
Score 100
Code Size 1079 Byte
Status
Exec Time 606 ms
Memory 60464 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
× 1
× 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 167 ms 38256 KB
subtask_01_01.txt 398 ms 52824 KB
subtask_01_02.txt 171 ms 45492 KB
subtask_01_03.txt 464 ms 53976 KB
subtask_01_04.txt 496 ms 60208 KB
subtask_01_05.txt 246 ms 44380 KB
subtask_01_06.txt 277 ms 47408 KB
subtask_01_07.txt 521 ms 58200 KB
subtask_01_08.txt 500 ms 60208 KB
subtask_01_09.txt 164 ms 38256 KB
subtask_01_10.txt 172 ms 45492 KB
subtask_01_11.txt 476 ms 56920 KB
subtask_01_12.txt 525 ms 60208 KB
subtask_01_13.txt 432 ms 55000 KB
subtask_01_14.txt 185 ms 45748 KB
subtask_01_15.txt 502 ms 58072 KB
subtask_01_16.txt 506 ms 60336 KB
subtask_01_17.txt 582 ms 60336 KB
subtask_01_18.txt 606 ms 60464 KB