Submission #79608

#	Time	Username	Problem	Language	Result	Execution time	Memory
79608		Dat160601	Park (BOI16_park)	C++17	100 / 100	549 ms	25564 KiB

park

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
int n,m,w,h;
int x[2009],y[2009],r[2009],pset[2009];
int side[5][5],ans[5][5];
vector < pair < int, pair<int,int> > > edge;
long long dist(long long a,long long b){
	return (long long)sqrtl(a*a+b*b);
}
int fset(int u){
	if(pset[u]==u) return u;
	return pset[u]=fset(pset[u]);
}
void unionset(int a,int b,int val){
	a=fset(a), b=fset(b);
	if(a==b) return;
	for(int i=1;i<=4;i++){
		if(fset(n+i)!=a) continue;
		for(int j=1;j<=4;j++){
			if(fset(n+j)!=b) continue;
			side[i][j]=val;
			side[j][i]=val;
		}
	}
	pset[a]=b;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin>>n>>m>>w>>h;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i]>>r[i];
	}
	for(int i=1;i<=n+4;i++){
		pset[i]=i;
		if(i>n) continue;
		for(int j=1;j<i;j++){
			int p=dist(x[i]-x[j],y[i]-y[j])-r[i]-r[j];
			p/=2;
			edge.pb(mp(p,mp(i,j)));
		}
		edge.pb(mp((x[i]-r[i])/2,mp(i,n+1)));
		edge.pb(mp((y[i]-r[i])/2,mp(i,n+2)));
		edge.pb(mp(((w-x[i])-r[i])/2,mp(i,n+3)));
		edge.pb(mp(((h-y[i])-r[i])/2,mp(i,n+4)));
	}
	sort(edge.begin(),edge.end());
	for(int i=0;i<(int)edge.size();i++){
		int u=edge[i].se.fi, v=edge[i].se.se;
		unionset(u,v,edge[i].fi);
	}
	ans[1][2]=ans[2][1]=min(side[2][1],min(side[2][4],side[2][3]));
	ans[1][4]=ans[4][1]=min(side[1][2],min(side[1][3],side[1][4]));
	ans[2][3]=ans[3][2]=min(side[3][2],min(side[3][1],side[3][4]));
	ans[3][4]=ans[4][3]=min(side[4][1],min(side[4][2],side[4][3]));
	ans[1][3]=ans[3][1]=min(side[1][2],min(side[1][3],min(side[4][2],side[4][3])));
	ans[2][4]=ans[4][2]=min(side[1][3],min(side[1][4],min(side[2][3],side[2][4])));
	while(m--){
		int r,corn;
		cin>>r>>corn;
		for(int i=1;i<=4;i++){
			if(i==corn || r<=ans[corn][i]) cout<<i;
		}
		cout<<"\n";
	}
}

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