Submission #535617

#	Time	Username	Problem	Language	Result	Execution time	Memory
535617		__Variatto	Park (BOI16_park)	C++17	27 / 100	2578 ms	452 KiB

park

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=2e3+10;
int fau[MAX];
int Find(int a){
    if(fau[a]==a)
        return a;
    return fau[a]=Find(fau[a]);
}
void Union(int a, int b){
    fau[Find(a)]=fau[Find(b)];
}
int n, m, w, h;
ll x[MAX], y[MAX], r[MAX];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n>>m>>w>>h;
    for(int i=1; i<=n; i++){
        cin>>x[i]>>y[i]>>r[i];
    }
    while(m--){
        int pro, e;
        cin>>pro>>e;
        for(int i=1; i<=n+4; i++)
            fau[i]=i;
        for(int i=1; i<=n; i++){
            if(y[i]-r[i]<2*pro) Union(i, n+1);
            if(w-(x[i]+r[i])<2*pro) Union(i, n+2);
            if(h-(y[i]+r[i])<2*pro) Union(i, n+3);
            if(x[i]-r[i]<2*pro) Union(i, n+4);
        }
/*        for(int i=1; i<=n+4; i++)
            cout<<i<<" "<<Find(i)<<"\n";
*/        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                ll odl=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
                odl-=(r[i]+r[j]);
                if(odl<2*pro)
                    Union(i, j);
            }
        }
        if(e==1){
            cout<<1;
            if(Find(n+1)!=Find(n+4)&&Find(n+1)!=Find(n+2)&&Find(n+1)!=Find(n+3))
                cout<<2;
            if(Find(n+1)!=Find(n+4)&&Find(n+4)!=Find(n+2)&&Find(n+1)!=Find(n+3)&&Find(n+2)!=Find(n+3))
                cout<<3;
            if(Find(n+1)!=Find(n+4)&&Find(n+3)!=Find(n+4)&&Find(n+2)!=Find(n+4))
                cout<<4;
        }
        if(e==2){
            if(Find(n+1)!=Find(n+4)&&Find(n+1)!=Find(n+2)&&Find(n+1)!=Find(n+3))
                cout<<1;
            cout<<2;
            if(Find(n+1)!=Find(n+2)&&Find(n+3)!=Find(n+2)&&Find(n+2)!=Find(n+4))
                cout<<3;
            if(Find(n+1)!=Find(n+3)&&Find(n+4)!=Find(n+2)&&Find(n+1)!=Find(n+2)&&Find(n+4)!=Find(n+3))
                cout<<4;
        }
        if(e==3){
            if(Find(n+1)!=Find(n+4)&&Find(n+4)!=Find(n+2)&&Find(n+1)!=Find(n+3)&&Find(n+2)!=Find(n+3))
                cout<<1;
            if(Find(n+1)!=Find(n+2)&&Find(n+3)!=Find(n+2)&&Find(n+2)!=Find(n+4))
                cout<<2;
            cout<<3;
            if(Find(n+3)!=Find(n+4)&&Find(n+3)!=Find(n+1)&&Find(n+2)!=Find(n+3))
                cout<<4;
        }
        if(e==4){
            if(Find(n+1)!=Find(n+4)&&Find(n+3)!=Find(n+4)&&Find(n+2)!=Find(n+4))
                cout<<1;
            if(Find(n+1)!=Find(n+3)&&Find(n+4)!=Find(n+2)&&Find(n+1)!=Find(n+2)&&Find(n+4)!=Find(n+3))
                cout<<2;
            if(Find(n+3)!=Find(n+4)&&Find(n+3)!=Find(n+1)&&Find(n+2)!=Find(n+3))
                cout<<3;
            cout<<4;
        }
        cout<<"\n";
    }
}

• Subtask 1: 27 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42