Submission #66569835

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from atcoder.dsu import DSU
uf = DSU(3000)
from heapq import *
hq = []
co = {}
def d(x, y):
    x1, y1 = co[x]
    x2, y2 = co[y]
    return abs(x1 - x2) + abs(y1 - y2)
v_lis = []
def new(id):
    for i in v_lis:
        if i == id:
            continue
        dist = d(i, id)
        heappush(hq, (dist,id,i))
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

from atcoder.dsu import DSU

uf = DSU(3000)
from heapq import *

hq = []
co = {}


def d(x, y):
    x1, y1 = co[x]
    x2, y2 = co[y]
    return abs(x1 - x2) + abs(y1 - y2)

v_lis = []
def new(id):
    for i in v_lis:
        if i == id:
            continue
        dist = d(i, id)
        heappush(hq, (dist,id,i))
    v_lis.append(id)

cur = 0
n, q = map(int, input().split())
nowcnt = n
cmp=n
for i in range(n):
    x, y = map(int, input().split())
    co[i]=(x,y)
for i in range(n):
    for j in range(i+1,n):
        heappush(hq,(d(i,j),i,j))
v_lis.extend(range(n))
for _ in range(q):
    a=list(map(int,input().split()))
    t=a[0]
    if t==1:
        x,y=a[1:]
        co[nowcnt]=(x,y)
        new(nowcnt)
        nowcnt+=1
        cmp+=1
    elif t==2:
        if cmp==1:
            print(-1)
            continue
        k=-1
        while hq and cmp>1:
            dist,u,v=heappop(hq)
            if not uf.same(u,v):
                k=dist
                heappush(hq,(dist,u,v))
                break
        if k==-1:
            print(-1)
        else:
            tmp=[]
            while hq:
                dist,u,v=heappop(hq)
                if dist==k:
                    if uf.merge(u,v):
                        cmp-=1
                else:
                    tmp.append((dist,u,v))
            hq=tmp
            heapify(hq)
            print(k)
    else:
        u,v=a[1]-1,a[2]-1
        print("Yes" if uf.same(u,v) else "No")

Submission Info

Judge Result