Submission #1242839

#TimeUsernameProblemLanguageResultExecution timeMemory
1242839sam230609Park (BOI16_park)C++20
100 / 100
243 ms49780 KiB
#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"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...