제출 #236415

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236415		alishahali1382	Park (BOI16_park)	C++14	100 / 100	381 ms	33400 KiB

park

#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 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42