Submission #7469229


Source Code Expand

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

N, Q = list(map(int, input().split()))
union = [i for i in range(N)]
level = [0 for i in range(N)]

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

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

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

	else:
		if root(union, A) == root(union, 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 961 Byte
Status
Exec Time 608 ms
Memory 64856 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 175 ms 38256 KB
subtask_01_01.txt 408 ms 53592 KB
subtask_01_02.txt 182 ms 45492 KB
subtask_01_03.txt 507 ms 58712 KB
subtask_01_04.txt 518 ms 60464 KB
subtask_01_05.txt 251 ms 44632 KB
subtask_01_06.txt 274 ms 47280 KB
subtask_01_07.txt 547 ms 61144 KB
subtask_01_08.txt 518 ms 60464 KB
subtask_01_09.txt 164 ms 38256 KB
subtask_01_10.txt 171 ms 45492 KB
subtask_01_11.txt 593 ms 64856 KB
subtask_01_12.txt 563 ms 60720 KB
subtask_01_13.txt 438 ms 55512 KB
subtask_01_14.txt 185 ms 45748 KB
subtask_01_15.txt 513 ms 60632 KB
subtask_01_16.txt 519 ms 60464 KB
subtask_01_17.txt 608 ms 60336 KB
subtask_01_18.txt 568 ms 60336 KB