제출 #1352530

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

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

int p[2005];

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

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

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

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

    vector<P> t(n);
    for(int i=0;i<n;i++){
        cin>>t[i].x>>t[i].y>>t[i].r;
    }

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

        int L=n, Rg=n+1, B=n+2, T=n+3;

        for(int i=0;i<n+4;i++) p[i]=i;

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

        for(int i=0;i<n;i++){
            if(t[i].x - t[i].r <= R) cum(i,L);
            if(w - t[i].x - t[i].r <= R) cum(i,Rg);
            if(t[i].y - t[i].r <= R) cum(i,B);
            if(h - t[i].y - t[i].r <= R) cum(i,T);
        }

        vector<int> v(5,1);

        if(fr(L)==fr(Rg)){
            v[1]=v[2]=v[3]=v[4]=0;
        }
        if(fr(B)==fr(T)){
            v[1]=v[2]=v[3]=v[4]=0;
        }
        if(fr(L)==fr(B)) v[1]=0;
        if(fr(B)==fr(Rg)) v[2]=0;
        if(fr(Rg)==fr(T)) v[3]=0;
        if(fr(T)==fr(L)) v[4]=0;

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