oj.uz

Submission #287841

# Submission time Handle Problem Language Result Execution time Memory
287841 2020-09-01T04:12:22 Z nandonathaniel Park (BOI16_park) C++14
100 / 100
 701 ms 66620 KB 
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXN=2010;

int w,h,par[MAXN];
long double minD[5][5],batas[5][5];

struct tree{
	int x,y,r;
};

tree a[MAXN];

int find(int x){
	if(par[x]==x)return par[x];
	return par[x]=find(par[x]);
}

bool sameSet(int a,int b){
	return find(a)==find(b);
}

void join(int a,int b){
	int ortua=find(a),ortub=find(b);
	par[ortua]=ortub;
}

long double jarak(int a,int b,int c,int d){
	return sqrt((long double)(c-a)*(long double)(c-a)+(long double)(d-b)*(long double)(d-b));
}

long double distCircle(int p,int q){
	return jarak(a[p].x,a[p].y,a[q].x,a[q].y)-(long double)a[p].r-(long double)a[q].r;
}

long double distBorder(int p,int q){  //1 bawah,2 kanan,3 atas,4 kiri
	if(q==1){
		return (long double)a[p].y-(long double)a[p].r;
	}
	else if(q==2){
		return (long double)w-(long double)a[p].x-(long double)a[p].r;
	}
	else if(q==3){
		return (long double)h-(long double)a[p].y-(long double)a[p].r;
	}
	else return (long double)a[p].x-(long double)a[p].r;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n,m,r,no;
	cin >> n >> m >> w >> h;
	for(int i=1;i<=n;i++){
		cin >> a[i].x >> a[i].y >> a[i].r;
		par[i]=i;
	}
	vector<pair<long double,pii> > edge;
	par[n+1]=n+1;par[n+2]=n+2;par[n+3]=n+3;par[n+4]=n+4;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			edge.push_back({distCircle(i,j),{i,j}});
		}
		for(int j=n+1;j<=n+4;j++){
			edge.push_back({distBorder(i,j-n),{i,j}});
		}
	}
	for(int i=1;i<=4;i++){
		for(int j=1;j<=4;j++)minD[i][j]=-1.0;
	}
	sort(edge.begin(),edge.end());
	for(auto isi : edge){
		join(isi.second.first,isi.second.second);
		for(int i=1;i<=4;i++){
			for(int j=i+1;j<=4;j++){
				if(sameSet(n+i,n+j) && minD[i][j]==-1.0)minD[i][j]=isi.first;
			}
		}
	}
	batas[1][1]=batas[2][2]=batas[3][3]=batas[4][4]=2000000005.0;
	batas[1][2]=batas[2][1]=min(minD[1][2],min(minD[1][3],minD[1][4]));
	batas[1][3]=batas[3][1]=min(min(minD[1][4],minD[2][3]),min(minD[1][3],minD[2][4]));
	batas[1][4]=batas[4][1]=min(minD[1][4],min(minD[2][4],minD[3][4]));
	batas[2][3]=batas[3][2]=min(minD[1][2],min(minD[2][3],minD[2][4]));
	batas[2][4]=batas[4][2]=min(min(minD[1][2],minD[3][4]),min(minD[1][3],minD[2][4]));
	batas[3][4]=batas[4][3]=min(minD[3][4],min(minD[1][3],minD[2][3]));
	while(m--){
		cin >> r >> no;
		r*=2;
		for(int i=1;i<=4;i++){
			if(r<=batas[no][i])cout << i;
		}
		cout << '\n';
	}
	return 0;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 66204 KB Output is correct
2 Correct 650 ms 66332 KB Output is correct
3 Correct 650 ms 66332 KB Output is correct
4 Correct 651 ms 66204 KB Output is correct
5 Correct 647 ms 66204 KB Output is correct
6 Correct 656 ms 66204 KB Output is correct
7 Correct 589 ms 66384 KB Output is correct
8 Correct 589 ms 66200 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2540 KB Output is correct
2 Correct 45 ms 2584 KB Output is correct
3 Correct 42 ms 2540 KB Output is correct
4 Correct 42 ms 2544 KB Output is correct
5 Correct 41 ms 2540 KB Output is correct
6 Correct 45 ms 2672 KB Output is correct
7 Correct 36 ms 1784 KB Output is correct
8 Correct 35 ms 1784 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 66204 KB Output is correct
2 Correct 650 ms 66332 KB Output is correct
3 Correct 650 ms 66332 KB Output is correct
4 Correct 651 ms 66204 KB Output is correct
5 Correct 647 ms 66204 KB Output is correct
6 Correct 656 ms 66204 KB Output is correct
7 Correct 589 ms 66384 KB Output is correct
8 Correct 589 ms 66200 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 43 ms 2540 KB Output is correct
12 Correct 45 ms 2584 KB Output is correct
13 Correct 42 ms 2540 KB Output is correct
14 Correct 42 ms 2544 KB Output is correct
15 Correct 41 ms 2540 KB Output is correct
16 Correct 45 ms 2672 KB Output is correct
17 Correct 36 ms 1784 KB Output is correct
18 Correct 35 ms 1784 KB Output is correct
19 Correct 696 ms 66460 KB Output is correct
20 Correct 686 ms 66456 KB Output is correct
21 Correct 690 ms 66620 KB Output is correct
22 Correct 701 ms 66460 KB Output is correct
23 Correct 694 ms 66460 KB Output is correct
24 Correct 638 ms 66464 KB Output is correct