Submission #349446

#	Time	Username	Problem	Language	Result	Execution time	Memory
349446		mp007mp	Park (BOI16_park)	C++14	58 / 100	326 ms	876 KiB

park

#include<bits/stdc++.h>
#define X second 
#define Y first
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
const ll maxn=3021;
ll inf = 1000ll*1000*1000*1000;
ll n,m,w,h;
pii cen[maxn];
ll r[maxn];
ll mark[maxn][4];
vector<ll> daste[4][4];
void seprate(ll u,ll v,ll mmkn[4][4]){
	bool exsist[4];
	fill(exsist,exsist+4,0);
	for(ll i:daste[u][v]){
		exsist[i]=1;
	}
	for(ll i=0;i<4;i++){
		for(ll j=i+1;j<4;j++){
			if((exsist[i] && !exsist[j]) || (exsist[j] && !exsist[i])){
				mmkn[i][j]=0;
				mmkn[j][i]=0;
			}
		}
	}
	return;
}
ll dist(pii a,pii b){
	ll res = 0;
	ll tmp = abs(a.X-b.X);
	tmp *= tmp;
	res += tmp;
	tmp = abs(a.Y-b.Y);
	tmp *= tmp;
	res += tmp;
	return res;
}
ll dist(ll a,ll b,ll c){
	ll tmp = a+b+c+c;
	tmp *= tmp;
	return tmp;
}
bool vasl(ll u,ll v,ll x){
	if(dist(cen[u],cen[v]) < dist(r[u],r[v],x)){
		return true;
	}else{
		return false;
	}
}
void dfs(ll v,ll c,ll x){
	for(ll i=1;i<=n;i++){
		if(!mark[i][c] && vasl(i,v,x)){
			mark[i][c]=1;
			dfs(i,c,x);
		}
	}
}
bool check(ll s,ll t,ll x){
	ll mmkn[4][4];
	for(ll i=0;i<4;i++){
		fill(mark[i],mark[i]+maxn,0);
		fill(mmkn[i],mmkn[i]+4,1);
	}
	for(ll i=1;i<=n;i++){
		if(!mark[i][0] && cen[i].Y-r[i]<x*2){
			mark[i][0]=1;
			dfs(i,0,x);
		}
	}
	for(ll i=1;i<=n;i++){
		if(!mark[i][1] && w-cen[i].X-r[i]<x*2){
			mark[i][1]=1;
			dfs(i,1,x);
		}
	}
	for(ll i=1;i<=n;i++){
		if(!mark[i][2] && h-cen[i].Y-r[i]<x*2){
			mark[i][2]=1;
			dfs(i,2,x);
		}
	}
	for(ll i=1;i<=n;i++){
		if(!mark[i][3] && cen[i].X-r[i]<x*2){
			mark[i][3]=1;
			dfs(i,3,x);
		}
	}
	for(ll i=1;i<=n;i++){
		for(ll v=0;v<4;v++){
			for(ll u=v+1;u<4;u++){
				if(mark[i][v] && mark[i][u]){
					seprate(v,u,mmkn);
				}
			}
		}
	}
	return mmkn[s][t];
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>w>>h;
	for(ll i=1;i<=n;i++){
		cin>>cen[i].X>>cen[i].Y>>r[i];
	}
	for(ll i=0;i<3;i++){
		daste[i][i+1].push_back(i+1);
	}
	daste[0][3].push_back(0);
	daste[0][2].push_back(1);
	daste[0][2].push_back(2);
	daste[1][3].push_back(2);
	daste[1][3].push_back(3);
	if(m==1){
		ll ent,shoa;
		cin>>shoa>>ent;
		ent--;
		for(ll i=0;i<4;i++){
			if(i==ent){
				cout<<i+1;
				continue;
			}
			if(check(ent,i,shoa)){
				cout<<i+1;
			}
		}cout<<"\n";
		return 0;
	}
	ll mmkn[4][4];
	for(ll i=0;i<4;i++){
		fill(mmkn[i],mmkn[i]+4,0);
	}
	for(ll i=0;i<4;i++){
		for(ll j=i+1;j<4;j++){
			ll l=-1,r=min(h,w)/4 + 100;
			while(r-l>1){
				ll mid = (r+l) >> 1;
				if(check(i,j,mid)){
					l = mid;
				}else{
					r = mid;
				}
			}
			mmkn[i][j] = l;
			mmkn[j][i] = l;
		}
		mmkn[i][i]=inf;
	}
	/*for(ll i=0;i<4;i++){
		for(ll j=0;j<4;j++){
			cout<<mmkn[i][j]<<" ";
		}cout<<"\n";
	}*/
	while(m--){
		ll ent,shoa;
		cin>>shoa>>ent;
		ent--;
		for(ll i=0;i<4;i++){
			if(mmkn[ent][i] >= shoa)cout<<i+1;
		}cout<<"\n";
	}
	/*for(int i=1;i<=n;i++){
		for(int j=0;j<4;j++){
			cout<<mark[i][j]<<" ";
		}cout<<"\n";
	}*/
	return 0;
}

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