Submission #535604

#	Time	Username	Problem	Language	Result	Execution time	Memory
535604		new_acc	Park (BOI16_park)	C++14	0 / 100	1165 ms	16152 KiB

park

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=2e3+10;
int mini[5][5],fau[N],n,m,w,h,c[N];
pair<int,int> z[N];
int odl[N][N];
int Find(int a){
	if(fau[a]==a) return a;
	return fau[a]=Find(fau[a]);
}
void Union(int a,int b){
	fau[Find(a)]=Find(fau[b]);
}
bool check(int x,int a,int b){
	if(a>b) swap(a,b);
	for(int i=1;i<=n+4;i++) fau[i]=i;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j) continue;
			if(odl[i][j]-c[i]-c[j]<x*2) Union(i,j);
		}
	}
	for(int i=1;i<=n;i++){
		if(z[i].se-c[i]<x*2) Union(i,n+1);
		if(w-z[i].fi-c[i]<x*2) Union(i,n+2);
		if(h-z[i].se-c[i]<x*2) Union(i,n+3);
		if(z[i].fi-c[i]<x*2) Union(i,n+4);
	}
	if(a==1 and b==2) return (Find(n+1)!=Find(n+2) and Find(n+1)!=Find(n+4) and Find(n+1)!=Find(n+3));
	if(a==1 and b==3) return (Find(n+2)!=Find(n+3) and Find(n+1)!=Find(n+4) and Find(n+1)!=Find(n+3) and Find(n+2)!=Find(n+4));
	if(a==1 and b==4) return (Find(n+3)!=Find(n+4) and Find(n+1)!=Find(n+4) and Find(n+2)!=Find(n+4));

	if(a==2 and b==3) return (Find(n+1)!=Find(n+2) and Find(n+2)!=Find(n+3) and Find(n+2)!=Find(n+4));
	if(a==2 and b==4) return (Find(n+1)!=Find(n+2) and Find(n+3)!=Find(n+4) and Find(n+1)!=Find(n+3) and Find(n+2)!=Find(n+4));
	//a=3 b=4
	return (Find(n+2)!=Find(n+3) and Find(n+3)!=Find(n+4) and Find(n+2)!=Find(n+4));
}
int bs(int x,int y){
	int res=0,pocz=0,kon=250*1000*1000;
	while(pocz<=kon){
		int sr=(pocz+kon)>>1;
		if(check(sr,x,y)) res=sr,pocz=sr+1;
		else kon=sr-1;
	}
	return res;
}
void solve(){
	cin>>n>>m>>w>>h;
	for(int i=1;i<=n;i++) cin>>z[i].fi>>z[i].se>>c[i];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
			odl[i][j]=sqrtl((ll)(z[i].fi-z[j].fi)*(ll)(z[i].fi-z[j].fi)+(ll)(z[i].se-z[j].se)*(ll)(z[i].se-z[j].se));
	}
	for(int i=1;i<=4;i++){
		for(int j=1;j<=4;j++){
			if(i==j) {mini[i][j]=1e9;continue;}
			if(i>j) mini[i][j]=mini[j][i];
			else mini[i][j]=bs(i,j);
		}
	}
	while(m--){
		int a,b;
		cin>>a>>b;
		if(mini[b][1]>=a) cout<<"1";
		if(mini[b][2]>=a) cout<<"2";
		if(mini[b][3]>=a) cout<<"3";
		if(mini[b][4]>=a) cout<<"4";
		cout<<"\n";
	}
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

• Subtask 1: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42