Submission #1323531

#TimeUsernameProblemLanguageResultExecution timeMemory
1323531NipphitchPark (BOI16_park)C++20
100 / 100
252 ms49872 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int N=2010;
struct D{
    int u,v,w;
    bool operator < (const D&o)const{
        return w<o.w;
    }
};

int n,q,p[N],sz[N],d[10][10],w,h,X[N],Y[N],R[N];
bool ans[10];
vector <D> edge;

void initial(){
    memset(d,-1,sizeof(d));
    for(int i=0;i<N;i++) p[i]=i,sz[i]=1;
}

int find_p(int u){
    return (u==p[u]?u:p[u]=find_p(p[u]));
}

void unite(int u,int v){
    u=find_p(u),v=find_p(v);
    if(u==v) return ;
    if(sz[u]<sz[v]) swap(u,v);
    sz[u]+=sz[v];
    p[v]=u;
}

bool ck(int u,int v,int r){
    return (d[u][v]<r);
}

int cal(int x1,int y1,int r1,int x2,int y2,int r2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))-r1-r2;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    initial();
    cin >> n >> q >> w >> h;
    for(int i=5;i<=n+4;i++){
        cin >> X[i] >> Y[i] >> R[i];
        edge.push_back({1,i,h-Y[i]-R[i]});
        edge.push_back({2,i,w-X[i]-R[i]});
        edge.push_back({3,i,Y[i]-R[i]});
        edge.push_back({4,i,X[i]-R[i]});
        for(int j=5;j<i;j++) edge.push_back({i,j,cal(X[i],Y[i],R[i],X[j],Y[j],R[j])});
    }
    sort(edge.begin(),edge.end());
    for(auto [u,v,w]:edge){
        unite(u,v);
        for(int i=1;i<=4;i++){
            for(int j=i+1;j<=4;j++){
                if(d[i][j]==-1 && find_p(i)==find_p(j)){
                    d[i][j]=d[j][i]=w;
                }
            }
        }
    }
    while(q--){
        int u,r;
        cin >> r >> u;
        r*=2;
        memset(ans,true,sizeof(ans));
        if(u==1){
            if(ck(1,2,r)) ans[3]=false;
            if(ck(1,3,r)) ans[2]=ans[3]=false;
            if(ck(1,4,r)) ans[4]=false;
            if(ck(2,3,r)) ans[2]=false;
            if(ck(2,4,r)) ans[3]=ans[4]=false;
            if(ck(3,4,r)) ans[2]=ans[3]=ans[4]=false;
        }
        else if(u==2){
            if(ck(1,2,r)) ans[3]=false;
            if(ck(1,3,r)) ans[1]=ans[4]=false;
            if(ck(1,4,r)) ans[4]=false;
            if(ck(2,3,r)) ans[1]=ans[3]=ans[4]=false;
            if(ck(2,4,r)) ans[3]=ans[4]=false;
            if(ck(3,4,r)) ans[1]=false;
        }
        else if(u==3){
            if(ck(1,2,r)) ans[1]=ans[2]=ans[4]=false;
            if(ck(1,3,r)) ans[1]=ans[4]=false;
            if(ck(1,4,r)) ans[4]=false;
            if(ck(2,3,r)) ans[2]=false;
            if(ck(2,4,r)) ans[1]=ans[2]=false;
            if(ck(3,4,r)) ans[1]=false;
        }
        else{
            if(ck(1,2,r)) ans[3]=false;
            if(ck(1,3,r)) ans[2]=ans[3]=false;
            if(ck(1,4,r)) ans[1]=ans[2]=ans[3]=false;
            if(ck(2,3,r)) ans[2]=false;
            if(ck(2,4,r)) ans[1]=ans[2]=false;
            if(ck(3,4,r)) ans[1]=false;
        }
        for(int i=1;i<=4;i++) if(ans[i]) cout << i;
        cout << "\n";
    }
}
/*
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...