oj.uz

Submission #236415

# Submission time Handle Problem Language Result Execution time Memory
236415 2020-06-02T05:42:06 Z alishahali1382 Park (BOI16_park) C++14
100 / 100
 381 ms 33400 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<ll, pii> E[MAXN*MAXN/2];
ll 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(ll &x, ll d){
	if (x==-1) x=d;
}

ll sq(ll d){
	ll res=ceil(sqrt(d));
	if (res*res==d) return res+1;
	return res;
}

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), {n+2, n+4}};
	E[cnt++]={(h), {n+1, n+3}};
	for (int i=1; i<=n; i++){
		cin>>X[i]>>Y[i]>>R[i];
		E[cnt++]={((Y[i]-R[i])), {i, n+1}};
		E[cnt++]={((w-X[i]-R[i])), {i, n+2}};
		E[cnt++]={((h-Y[i]-R[i])), {i, n+3}};
		E[cnt++]={((X[i]-R[i])), {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++]={((sq(d)-R[i]-R[j])), {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;
		ll d=E[i].first;
		join(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(ans23, d);
			upd(ans14, 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;
		r*=2;
		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<ans34) 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

8 1
1000000000 1000000000
200000000 384529926 2459575
400000000 269059852 2459575
400000000 499999960 2459575
600000000 384529886 2459575
600000000 615469994 2459575
800000000 499999920 2459575
400000000 38119745 2459575
597768045 995105726 2459576
113010479 3



*/

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 31864 KB Output is correct
2 Correct 345 ms 31992 KB Output is correct
3 Correct 342 ms 31856 KB Output is correct
4 Correct 347 ms 31864 KB Output is correct
5 Correct 346 ms 31864 KB Output is correct
6 Correct 344 ms 31872 KB Output is correct
7 Correct 282 ms 31744 KB Output is correct
8 Correct 282 ms 31960 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1016 KB Output is correct
2 Correct 37 ms 1024 KB Output is correct
3 Correct 36 ms 1016 KB Output is correct
4 Correct 36 ms 1016 KB Output is correct
5 Correct 39 ms 1152 KB Output is correct
6 Correct 38 ms 1144 KB Output is correct
7 Correct 33 ms 632 KB Output is correct
8 Correct 35 ms 1944 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 31864 KB Output is correct
2 Correct 345 ms 31992 KB Output is correct
3 Correct 342 ms 31856 KB Output is correct
4 Correct 347 ms 31864 KB Output is correct
5 Correct 346 ms 31864 KB Output is correct
6 Correct 344 ms 31872 KB Output is correct
7 Correct 282 ms 31744 KB Output is correct
8 Correct 282 ms 31960 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 38 ms 1016 KB Output is correct
12 Correct 37 ms 1024 KB Output is correct
13 Correct 36 ms 1016 KB Output is correct
14 Correct 36 ms 1016 KB Output is correct
15 Correct 39 ms 1152 KB Output is correct
16 Correct 38 ms 1144 KB Output is correct
17 Correct 33 ms 632 KB Output is correct
18 Correct 35 ms 1944 KB Output is correct
19 Correct 377 ms 33400 KB Output is correct
20 Correct 378 ms 33344 KB Output is correct
21 Correct 377 ms 33272 KB Output is correct
22 Correct 374 ms 33144 KB Output is correct
23 Correct 381 ms 33144 KB Output is correct
24 Correct 319 ms 33400 KB Output is correct