제출 #1352534

#제출 시각아이디문제언어결과실행 시간메모리
1352534vjudge1Park (BOI16_park)C++17
0 / 100
2017 ms908 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;

struct pii{
    int x,y,r;
};

int p[2005];
int mark[2005][5], adj[5][5];

int fr(int x){
    return p[x]==x?x:p[x]=fr(p[x]);
}

void cum(int a,int b){
    a=fr(a); b=fr(b);
    if(a!=b) p[a]=b;
}

void upd(int i){
    for(int j=1;j<=4;j++){
        if(j==i) continue;
        adj[i][j]=adj[j][i]=1;
    }
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);

    int n,m; cin>>n>>m;
    int w,h; cin>>w>>h;

    vector<pii> a(n);
    for(int i=0;i<n;i++) cin>>a[i].x>>a[i].y>>a[i].r;

    while(m--){
        int R,st; cin>>R>>st;

        for(int i=0;i<n;i++){
            p[i]=i;
            for(int j=1;j<=4;j++) mark[i][j]=0;
        }
        for(int i=1;i<=4;i++)
            for(int j=1;j<=4;j++) adj[i][j]=0;

        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                int dx=a[i].x-a[j].x;
                int dy=a[i].y-a[j].y;
                int rr=a[i].r+a[j].r+2*R;
                if(dx*dx+dy*dy<=rr*rr) cum(i,j);
            }
        }

        for(int i=0;i<n;i++){
            int r=fr(i);
            if(a[i].x-a[i].r<=R) mark[r][1]=1; // left
            if(a[i].y-a[i].r<=R) mark[r][2]=1; // bottom
            if(w-a[i].x-a[i].r<=R) mark[r][3]=1; // right
            if(h-a[i].y-a[i].r<=R) mark[r][4]=1; // top
        }

        for(int i=0;i<n;i++){
            if(fr(i)!=i) continue;

            if(mark[i][1]&&mark[i][4]) upd(4);
            if(mark[i][4]&&mark[i][3]) upd(3);
            if(mark[i][3]&&mark[i][2]) upd(2);
            if(mark[i][1]&&mark[i][2]) upd(1);

            if(mark[i][4]&&mark[i][2]){
                adj[4][2]=adj[2][4]=1;
                adj[4][3]=adj[3][4]=1;
                adj[1][2]=adj[2][1]=1;
                adj[1][3]=adj[3][1]=1;
            }
            if(mark[i][1]&&mark[i][3]){
                adj[4][1]=adj[1][4]=1;
                adj[4][2]=adj[2][4]=1;
                adj[3][1]=adj[1][3]=1;
                adj[3][2]=adj[2][3]=1;
            }
        }

        for(int i=1;i<=4;i++){
            if(!adj[st][i]) cout<<i;
        }
        cout<<"\n";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...