Submission #1193869

#TimeUsernameProblemLanguageResultExecution timeMemory
1193869irmuunPark (BOI16_park)C++20
100 / 100
284 ms26004 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define ff first #define ss second #define all(s) s.begin(),s.end() #define rall(s) s.rbegin(),s.rend() struct dsu{ int n; vector<int>sz,par; dsu(int n):n(n){ sz.resize(n); par.resize(n); fill(all(sz),1); iota(all(par),0); } int find(int x){ if(par[x]==x) return x; return par[x]=find(par[x]); } bool same(int x,int y){ x=find(x); y=find(y); return x==y; } void merge(int x,int y){ x=find(x); y=find(y); if(x!=y){ if(sz[x]<sz[y]) swap(x,y); par[y]=x; sz[x]+=x; } } }; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); auto dist=[&](int x1,int y1,int x2,int y2,int r1,int r2){ return sqrt(1ll*(x1-x2)*(x1-x2)+1ll*(y1-y2)*(y1-y2))-r1-r2; }; int n,m; cin>>n>>m; int w,h; cin>>w>>h; int x[n],y[n],r[n]; for(int i=0;i<n;i++){ cin>>x[i]>>y[i]>>r[i]; } int E[m],R[m]; for(int i=0;i<m;i++){ cin>>R[i]>>E[i]; R[i]*=2; E[i]--; } vector<array<int,3>>edge; for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ int d=(int)dist(x[i],y[i],x[j],y[j],r[i],r[j]); edge.pb({d,i+4,j+4}); } edge.pb({x[i]-r[i],0,i+4}); edge.pb({w-x[i]-r[i],2,i+4}); edge.pb({y[i]-r[i],1,i+4}); edge.pb({h-y[i]-r[i],3,i+4}); } sort(all(edge)); auto mx=vector(4,vector<int>(4,1e9)); dsu ds(n+4); for(int i=0;i<edge.size();i++){ ds.merge(edge[i][1],edge[i][2]); for(int j=0;j<4;j++){ for(int k=j+1;k<4;k++){ if(ds.same(j,k)){ mx[j][k]=min(mx[j][k],edge[i][0]); mx[k][j]=min(mx[k][j],edge[i][0]); } } } } auto ans=vector(4,vector<int>(4,1e9)); ans[0][1]=ans[1][0]=min({mx[1][0],mx[1][3],mx[1][2]}); ans[1][2]=ans[2][1]=min({mx[2][1],mx[2][0],mx[2][3]}); ans[2][3]=ans[3][2]=min({mx[3][2],mx[3][1],mx[3][0]}); ans[3][0]=ans[0][3]=min({mx[0][3],mx[0][2],mx[0][1]}); ans[0][2]=ans[2][0]=min({mx[0][2],mx[1][3],mx[0][1],mx[2][3]}); ans[1][3]=ans[3][1]=min({mx[0][2],mx[1][3],mx[1][2],mx[0][3]}); for(int i=0;i<m;i++){ for(int j=0;j<4;j++){ if(ans[E[i]][j]>=R[i]){ cout<<j+1; } } cout<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...