oj.uz

Submission #236409

# Submission time Handle Problem Language Result Execution time Memory
236409 2020-06-02T04:52:33 Z alishahali1382 Park (BOI16_park) C++14
0 / 100
 588 ms 63480 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=2010, LOG=20;

ll n, m, k, w, h, x, y, t, r, s, cnt;
ll X[MAXN], Y[MAXN], R[MAXN];
int par[MAXN];
pair<ld, pii> E[MAXN*MAXN/2];
ld ans12=-1, ans13=-1, ans14=-1, ans23=-1, ans24=-1, ans34=-1;

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

void join(int x, int y){
	par[getpar(x)]=getpar(y);
}

inline void upd(ld &x, ld d){
	if (x==-1) x=d;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m>>w>>h;
	E[cnt++]={(w/2.), {n+2, n+4}};
	E[cnt++]={(h/2.), {n+1, n+3}};
	for (int i=1; i<=n; i++){
		cin>>X[i]>>Y[i]>>R[i];
		E[cnt++]={((Y[i]-R[i])/2.), {i, n+1}};
		E[cnt++]={((w-X[i]-R[i])/2.), {i, n+2}};
		E[cnt++]={((h-Y[i]-R[i])/2.), {i, n+3}};
		E[cnt++]={((X[i]-R[i])/2.), {i, n+4}};
	}
	for (int i=1; i<=n; i++) for (int j=i+1; j<=n; j++){
		ll dx=X[i]-X[j], dy=Y[i]-Y[j], d=dx*dx+dy*dy;
		E[cnt++]={((sqrt(d)-R[i]-R[j])/2.), {i, j}};
	}
	sort(E, E+cnt);
	//reverse(E, E+cnt);
	iota(par, par+MAXN, 0);
	for (int i=0; i<cnt; i++){
		int x=E[i].second.first, y=E[i].second.second;
		ld d=E[i].first;
		join(x, y);
		//if (d<=1) debug2(x, y)
		if (getpar(n+1)==getpar(n+2)){
			upd(ans12, d);
			upd(ans24, d);
			upd(ans23, d);
		}
		if (getpar(n+1)==getpar(n+3)){
			upd(ans12, d);
			upd(ans13, d);
			upd(ans24, d);
			upd(ans34, d);
		}
		if (getpar(n+1)==getpar(n+4)){
			upd(ans12, d);
			upd(ans13, d);
			upd(ans14, d);
		}
		if (getpar(n+2)==getpar(n+3)){
			upd(ans13, d);
			upd(ans23, d);
			upd(ans34, d);
		}
		if (getpar(n+2)==getpar(n+4)){
			upd(ans13, d);
			upd(ans14, d);
			upd(ans23, d);
			upd(ans24, d);
		}
		if (getpar(n+3)==getpar(n+4)){
			upd(ans14, d);
			upd(ans24, d);
			upd(ans34, d);
		}
	}
	while (m--){
		cin>>r>>s;
		if (s==1){
			cout<<"1";
			if (r<ans12) cout<<"2";
			if (r<ans13) cout<<"3";
			if (r<ans14) cout<<"4";
		}
		if (s==2){
			if (r<ans12) cout<<"1";
			cout<<"2";
			if (r<ans23) cout<<"3";
			if (r<ans24) cout<<"4";
		}
		if (s==3){
			if (r<ans13) cout<<"1";
			if (r<ans23) cout<<"2";
			cout<<"3";
			if (r<ans24) cout<<"4";
		}
		if (s==4){
			if (r<ans14) cout<<"1";
			if (r<ans24) cout<<"2";
			if (r<ans34) cout<<"3";
			cout<<"4";
		}
		cout<<"\n";
	}
	
	
	return 0;
}
/*
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1

*/

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 63352 KB Output is correct
2 Correct 588 ms 63400 KB Output is correct
3 Correct 578 ms 63480 KB Output is correct
4 Correct 583 ms 63328 KB Output is correct
5 Correct 588 ms 63356 KB Output is correct
6 Correct 577 ms 63356 KB Output is correct
7 Correct 479 ms 63224 KB Output is correct
8 Incorrect 489 ms 63352 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 1408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 63352 KB Output is correct
2 Correct 588 ms 63400 KB Output is correct
3 Correct 578 ms 63480 KB Output is correct
4 Correct 583 ms 63328 KB Output is correct
5 Correct 588 ms 63356 KB Output is correct
6 Correct 577 ms 63356 KB Output is correct
7 Correct 479 ms 63224 KB Output is correct
8 Incorrect 489 ms 63352 KB Output isn't correct
9 Halted 0 ms 0 KB -