Submission #525160

#	Time	Username	Problem	Language	Result	Execution time	Memory
525160		codr0	Park (BOI16_park)	C++14	100 / 100	2478 ms	34020 KiB

park

// Code by Parsa Eslami
 
#include <bits/stdc++.h>
#define int long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cout<<#x<<": "<<x<<'\n';
 
using namespace std;
typedef pair<int,int> pii;
const int N=2e3+10;
vector<int> adj[N];
int dis[5][5],n,h,w;
bool mark[N];
vector<pair<pii,int>> cy;

	void dfs(int v){
		mark[v]=1;
		for(int u:adj[v]) if(!mark[u]) dfs(u);
	}

	void FILL_adj(int X){
		FOR(i,0,N-1) adj[i].clear();
		FOR(i,0,n-1) FOR(j,0,n-1) if(i!=j){
			int X1=cy[i].F.F;
			int Y1=cy[i].F.S;
			int R1=cy[i].S;
			int X2=cy[j].F.F;
			int Y2=cy[j].F.S;
			int R2=cy[j].S;
			long long dis=(abs(X1-X2)*abs(X1-X2))+(abs(Y1-Y2)*abs(Y1-Y2));
			long long go=(R1+R2+2*X)*(R1+R2+2*X);
			if(go>dis){
				adj[i+5].pb(j+5);
			}
		}
		FOR(i,0,n-1){
			int XX=cy[i].F.F;
			int YY=cy[i].F.S;
			int R=cy[i].S;
			if(XX-2*X-R<0){
				adj[i+5].pb(4);
				adj[4].pb(i+5);
			}
			if(XX+2*X+R>h){
				adj[i+5].pb(2);
				adj[2].pb(i+5);
			}
			if(YY-2*X-R<0){
				adj[i+5].pb(1);
				adj[1].pb(i+5);
			}
			if(YY+2*X+R>w){
				adj[i+5].pb(3);
				adj[3].pb(i+5);
			}
		}
	}

	void pre(){
		FOR(i,1,4) dis[i][i]=2e9;
		FOR(i,1,4) FOR(j,i+1,4){
			//dis[i][j] & dis[j][i]
			int l=-1,r=2e9;
			while(r-l>1){
				int mid=(r+l)/2;
				FOR(wz,0,N-1) mark[wz]=0;
				FILL_adj(mid);
				dfs(i);
				if(mark[j]) r=mid;
				else l=mid;
			}
			dis[i][j]=dis[j][i]=r;
		}
	}

	int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	int m;
	cin>>n>>m>>h>>w;
	FOR(i,1,n){
		int x,y,r; cin>>x>>y>>r;
		cy.pb({{x,y},r});
	}
	pre();
	FOR(i,1,m){
		int r,e; cin>>r>>e;
		bool ans[5]; FOR(i,1,4) ans[i]=1;
		FOR(i,1,4) FOR(j,i+1,4) if(dis[i][j]<=r){
			if(j==i+3){
				if(e!=1) ans[1]=0;
				else{
					ans[3]=ans[2]=ans[4]=0;
				}
			}
			if(j==(i+1)){
				if(e!=j) ans[j]=0;
				else{
					FOR(w,1,4) if(w!=j) ans[w]=0;
				}
			}
			if(j==(i+2)){
				if(i==2){
					if(e<3){
						ans[3]=ans[4]=0;
					}else{
						ans[1]=ans[2]=0;
					}
				}else{
					if(e==2||e==3){
						ans[1]=ans[4]=0;
					}else{
						ans[2]=ans[3]=0;
					}
				}
			}
		}
		FOR(i,1,4) if(ans[i]) cout<<i;
		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: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42