oj.uz

Submission #79608

# Submission time Handle Problem Language Result Execution time Memory
79608 2018-10-15T06:02:18 Z Dat160601 Park (BOI16_park) C++17
100 / 100
 549 ms 25564 KB 
#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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 25288 KB Output is correct
2 Correct 324 ms 25288 KB Output is correct
3 Correct 338 ms 25288 KB Output is correct
4 Correct 322 ms 25288 KB Output is correct
5 Correct 316 ms 25288 KB Output is correct
6 Correct 317 ms 25288 KB Output is correct
7 Correct 303 ms 25376 KB Output is correct
8 Correct 288 ms 25376 KB Output is correct
9 Correct 2 ms 25376 KB Output is correct
10 Correct 2 ms 25376 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 25376 KB Output is correct
2 Correct 212 ms 25376 KB Output is correct
3 Correct 202 ms 25376 KB Output is correct
4 Correct 204 ms 25376 KB Output is correct
5 Correct 202 ms 25376 KB Output is correct
6 Correct 205 ms 25376 KB Output is correct
7 Correct 204 ms 25376 KB Output is correct
8 Correct 389 ms 25376 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 25288 KB Output is correct
2 Correct 324 ms 25288 KB Output is correct
3 Correct 338 ms 25288 KB Output is correct
4 Correct 322 ms 25288 KB Output is correct
5 Correct 316 ms 25288 KB Output is correct
6 Correct 317 ms 25288 KB Output is correct
7 Correct 303 ms 25376 KB Output is correct
8 Correct 288 ms 25376 KB Output is correct
9 Correct 2 ms 25376 KB Output is correct
10 Correct 2 ms 25376 KB Output is correct
11 Correct 200 ms 25376 KB Output is correct
12 Correct 212 ms 25376 KB Output is correct
13 Correct 202 ms 25376 KB Output is correct
14 Correct 204 ms 25376 KB Output is correct
15 Correct 202 ms 25376 KB Output is correct
16 Correct 205 ms 25376 KB Output is correct
17 Correct 204 ms 25376 KB Output is correct
18 Correct 389 ms 25376 KB Output is correct
19 Correct 514 ms 25432 KB Output is correct
20 Correct 507 ms 25564 KB Output is correct
21 Correct 522 ms 25564 KB Output is correct
22 Correct 538 ms 25564 KB Output is correct
23 Correct 549 ms 25564 KB Output is correct
24 Correct 500 ms 25564 KB Output is correct