Submission #66578802

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 
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:
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
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 not uf.same(u,v):
                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")
*/
#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
using atcoder::dsu;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    vector<pair<int,int>> co(n+q);
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        co[i]={x,y};
    }
    priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<tuple<int,int,int>>> hq;
    for(int i=0;i<n;i++){
        auto [xi,yi]=co[i];
        for(int j=i+1;j<n;j++){
            auto [xj,yj]=co[j];
            hq.emplace(abs(xi-xj)+abs(yi-yj),i,j);
        }
    }
    dsu uf(n+q);
    int active=n,comp=n,cnt=n;
    while(q--){
        int t;
        cin>>t;
        if(t==1){
            int x,y;
            cin>>x>>y;
            co[cnt]={x,y};
            for(int i=0;i<active;i++){
                auto [xi,yi]=co[i];
                hq.emplace(abs(xi-x)+abs(yi-y),i,cnt);
            }
            cnt++;active++;comp++;
        } else if(t==2){
            if(comp<=1){
                cout<<-1<<"\n";
                continue;
            }
            int w;
            while(!hq.empty()){
                auto [d,u,v]=hq.top();
                hq.pop();
                if(u<active && v<active && !uf.same(u,v)){
                    w=d;
                    hq.emplace(d,u,v);
                    break;
                }
            }
            if(hq.empty() && (comp>1)){
                cout<<-1<<"\n";
                continue;
            }
            while(!hq.empty() && get<0>(hq.top())==w){
                auto [_,u,v]=hq.top();
                hq.pop();
                if(u<active && v<active && !uf.same(u,v)){
                    uf.merge(u,v);
                    comp--;
                }
            }
            cout<<w<<"\n";
        } else {
            int u,v;
            cin>>u>>v;
            --u;--v;
            cout<<(uf.same(u,v)?"Yes":"No")<<"\n";
        }
    }
    return 0;
}

Submission Info

Judge Result