Submission #66576059
Source Code Expand
Copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
import sys
from atcoder.dsu import DSU
from heapq import *
n,q=map(int,input().split())
co=[None]*(n+q)
for i in range(n):
co[i]=tuple(map(int,input().split()))
hq=[]
for i in range(n):
xi,yi=co[i]
for j in range(i+1,n):
xj,yj=co[j]
heappush(hq,(abs(xi-xj)+abs(yi-yj),i,j))
uf=DSU(n+q)
active=comp=n
cnt=n
for _ in range(q):
l=list(map(int,input().split()))
t=l[0]
if t==1:
x,y=l[1],l[2]
co[cnt]=(x,y)
for i in range(active):
xi,yi=co[i]
heappush(hq,(abs(xi-x)+abs(yi-y),i,cnt))
cnt+=1;active+=1;comp+=1
elif t==2:
if comp<=1:
print(-1);continue
while hq:
d,u,v=heappop(hq)
if u<active and v<active and not uf.same(u,v):
w=d
heappush(hq,(d,u,v))
break
else:
print(-1);continue
while hq and hq[0][0]==w:
_,u,v=heappop(hq)
if u<active and v<active and uf.merge(u,v):
comp-=1
print(w)
else:
u,v=l[1]-1,l[2]-1
print("Yes" if uf.same(u,v)else"No")
Submission Info
Submission Time
2025-06-07 22:32:41
Task
F - Connecting Points
User
juten
Language
Python (PyPy 3.10-v7.3.12)
Score
0
Code Size
1184 Byte
Status
WA
Exec Time
2239 ms
Memory
620884 KiB
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
0 / 500
Status
Set Name
Test Cases
Sample
00_sample_00.txt
All
00_sample_00.txt, 01_test_00.txt, 01_test_01.txt, 01_test_02.txt, 01_test_03.txt, 01_test_04.txt, 01_test_05.txt, 01_test_06.txt, 01_test_07.txt, 01_test_08.txt, 01_test_09.txt, 01_test_10.txt, 01_test_11.txt, 01_test_12.txt, 01_test_13.txt, 01_test_14.txt, 01_test_15.txt, 01_test_16.txt, 01_test_17.txt, 01_test_18.txt, 01_test_19.txt, 01_test_20.txt, 01_test_21.txt, 01_test_22.txt, 01_test_23.txt, 01_test_24.txt, 01_test_25.txt, 01_test_26.txt, 01_test_27.txt, 01_test_28.txt, 01_test_29.txt, 01_test_30.txt, 01_test_31.txt, 01_test_32.txt, 01_test_33.txt, 01_test_34.txt, 01_test_35.txt, 01_test_36.txt, 01_test_37.txt, 01_test_38.txt, 01_test_39.txt, 01_test_40.txt, 01_test_41.txt, 01_test_42.txt, 01_test_43.txt
Case Name
Status
Exec Time
Memory
00_sample_00.txt
AC 123 ms
84684 KiB
01_test_00.txt
AC 641 ms
274840 KiB
01_test_01.txt
WA 678 ms
275832 KiB
01_test_02.txt
TLE 2239 ms
620884 KiB
01_test_03.txt
WA 669 ms
275744 KiB
01_test_04.txt
AC 1503 ms
430096 KiB
01_test_05.txt
WA 1556 ms
430320 KiB
01_test_06.txt
WA 1176 ms
367632 KiB
01_test_07.txt
WA 657 ms
276000 KiB
01_test_08.txt
WA 1210 ms
373208 KiB
01_test_09.txt
WA 1098 ms
339928 KiB
01_test_10.txt
WA 1099 ms
340308 KiB
01_test_11.txt
WA 1538 ms
430784 KiB
01_test_12.txt
AC 632 ms
275196 KiB
01_test_13.txt
AC 712 ms
275860 KiB
01_test_14.txt
TLE 2237 ms
574444 KiB
01_test_15.txt
AC 665 ms
275124 KiB
01_test_16.txt
AC 1479 ms
430124 KiB
01_test_17.txt
AC 1529 ms
430228 KiB
01_test_18.txt
AC 1195 ms
372848 KiB
01_test_19.txt
AC 658 ms
274696 KiB
01_test_20.txt
AC 1187 ms
371300 KiB
01_test_21.txt
AC 1053 ms
339700 KiB
01_test_22.txt
AC 1103 ms
339348 KiB
01_test_23.txt
AC 1493 ms
429828 KiB
01_test_24.txt
TLE 2220 ms
245104 KiB
01_test_25.txt
WA 1461 ms
341424 KiB
01_test_26.txt
WA 1210 ms
372420 KiB
01_test_27.txt
WA 1139 ms
372376 KiB
01_test_28.txt
WA 1448 ms
336880 KiB
01_test_29.txt
WA 1183 ms
345296 KiB
01_test_30.txt
WA 1183 ms
374132 KiB
01_test_31.txt
WA 1161 ms
366696 KiB
01_test_32.txt
WA 1204 ms
367944 KiB
01_test_33.txt
WA 1159 ms
367876 KiB
01_test_34.txt
WA 1177 ms
372776 KiB
01_test_35.txt
AC 1205 ms
371884 KiB
01_test_36.txt
WA 1120 ms
368292 KiB
01_test_37.txt
WA 1195 ms
373352 KiB
01_test_38.txt
AC 1182 ms
373240 KiB
01_test_39.txt
AC 1137 ms
350444 KiB
01_test_40.txt
AC 1504 ms
430896 KiB
01_test_41.txt
AC 1156 ms
372464 KiB
01_test_42.txt
AC 1694 ms
508408 KiB
01_test_43.txt
AC 120 ms
84480 KiB