Submission #66572190

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* Original Python code:
from atcoder.dsu import DSU
from heapq import *
uf=DSU(3000)
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)
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))
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

/* Original Python code:
from atcoder.dsu import DSU
from heapq import *
uf=DSU(3000)
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)
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:
            while hq and hq[0][0]==k:
                _,u,v=heappop(hq)
                if uf.merge(u,v):cmp-=1
            print(k)
    else:
        u,v=a[1]-1,a[2]-1;print("Yes" if uf.same(u,v) else "No")
*/
#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
using atcoder::dsu;
int main(){
    dsu uf(3000);
    priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<tuple<int,int,int>>> hq;
    unordered_map<int,pair<int,int>> co;
    auto d=[&](int x,int y){auto a=co[x],b=co[y];return abs(a.first-b.first)+abs(a.second-b.second);};
    vector<int> v_lis;
    int n,q;cin>>n>>q;
    int nowcnt=n,cmp=n;
    for(int i=0;i<n;i++){int x,y;cin>>x>>y;co[i]={x,y};}
    for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)hq.emplace(d(i,j),i,j);
    for(int i=0;i<n;i++)v_lis.push_back(i);
    while(q--){
        int t;cin>>t;
        if(t==1){
            int x,y;cin>>x>>y;
            co[nowcnt]={x,y};
            for(int i:v_lis){
                if(i==nowcnt)continue;
                hq.emplace(d(nowcnt,i),nowcnt,i);
            }
            v_lis.push_back(nowcnt);
            nowcnt++;cmp++;
        } else if(t==2){
            if(cmp==1){cout<<-1<<"\n";continue;}
            int k=-1;
            while(!hq.empty()&&cmp>1){
                auto [dist,u,v]=hq.top();hq.pop();
                if(!uf.same(u,v)){k=dist;hq.emplace(dist,u,v);break;}
            }
            if(k==-1)cout<<-1<<"\n";
            else{
                while(!hq.empty()&&get<0>(hq.top())==k){
                    auto [_,u,v]=hq.top();hq.pop();
                    if(uf.merge(u,v))cmp--;
                }
                cout<<k<<"\n";
            }
        } else {
            int u,v;cin>>u>>v;u--,v--;
            cout<<(uf.same(u,v)?"Yes":"No")<<"\n";
        }
    }
    return 0;
}

Submission Info

Judge Result