Submission #1242839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242839		sam230609	Park (BOI16_park)	C++20	100 / 100	243 ms	49780 KiB

park

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
ll x[2023],y[2023],r[2023],p[2023],g[5][5];
struct E {ll a,b,w;}; ll findP(ll a) {return p[a]<0?a:p[a]=findP(p[a]);}
void unite(ll a, ll b){
    a=findP(a); b=findP(b); if(a==b) return; if(p[a]>p[b]) swap(a,b); p[a]+=p[b]; p[b]=a;
}
bool f(ll a, ll b, ll r) {return g[a][b]<r;}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll n,q,w,h; cin >>n>>q>>w>>h; vector<E> ee;
    for(ll i=5;i<=n+4;i++){
        cin >>x[i]>>y[i]>>r[i];
        ee.pb({1,i,h-y[i]-r[i]}); ee.pb({2,i,w-x[i]-r[i]}); ee.pb({3,i,y[i]-r[i]}); ee.pb({4,i,x[i]-r[i]});
        for(ll j=5;j<i;j++) ee.pb({j,i,(ll)(sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))-r[i]-r[j])});
    }sort(ee.begin(),ee.end(),[](E &i, E &j) {return i.w<j.w;});
    memset(g,-1,sizeof(g)); memset(p,-1,sizeof(p));
    for(auto[a,b,w]:ee){
        unite(a,b);
        for(ll i=1;i<=4;i++){
            for(ll j=i+1;j<=4;j++){
                if(g[i][j]==-1 && findP(i)==findP(j)) g[i][j]=g[j][i]=w;
            }
        }
    }while(q--){
        ll R,pp; cin >>R>>pp; R*=2; vector<ll> ok(5,1);
        if(pp==1){
            if(f(3,4,R)) ok[2]=ok[3]=ok[4]=0; if(f(4,1,R)) ok[4]=0; if(f(1,2,R)) ok[3]=0;
            if(f(2,3,R)) ok[2]=0; if(f(1,3,R)) ok[2]=ok[3]=0; if(f(2,4,R)) ok[4]=ok[3]=0;
        }else if(pp==2){
            if(f(3,4,R)) ok[1]=0; if(f(4,1,R)) ok[4]=0; if(f(1,2,R)) ok[3]=0;
            if(f(2,3,R)) ok[1]=ok[3]=ok[4]=0; if(f(1,3,R)) ok[1]=ok[4]=0; if(f(2,4,R)) ok[4]=ok[3]=0;
        }else if(pp==3){
            if(f(3,4,R)) ok[1]=0; if(f(4,1,R)) ok[4]=0; if(f(1,2,R)) ok[1]=ok[2]=ok[4]=0;
            if(f(2,3,R)) ok[2]=0; if(f(1,3,R)) ok[1]=ok[4]=0; if(f(2,4,R)) ok[1]=ok[2]=0;
        }else{
            if(f(3,4,R)) ok[1]=0; if(f(4,1,R)) ok[1]=ok[2]=ok[3]=0; if(f(1,2,R)) ok[3]=0;
            if(f(2,3,R)) ok[2]=0; if(f(1,3,R)) ok[2]=ok[3]=0; if(f(2,4,R)) ok[1]=ok[2]=0;
        }for(ll i=1;i<=4;i++) if(ok[i]) cout <<i;
        cout << "\n";
    }
}

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