Submission #349408

#	Time	Username	Problem	Language	Result	Execution time	Memory
349408		mp007mp	Park (BOI16_park)	C++14	0 / 100	184 ms	876 KiB

park

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

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