oj.uz

Submission #535599

# Submission time Handle Problem Language Result Execution time Memory
535599 2022-03-10T16:20:26 Z new_acc Park (BOI16_park) C++14
0 / 100
 2500 ms 1620 KB 
#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<ll,ll> z[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;
			ll odl=(ll)sqrtl((z[i].fi-z[j].fi)*(z[i].fi-z[j].fi)+(z[i].se-z[j].se)*(z[i].se-z[j].se));
			if(odl-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=1e9+10;
	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<=4;i++){
		for(int j=1;j<=4;j++){
			if(i==j) {mini[i][j]=1e9;continue;}
			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(){
	solve();
}

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2596 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 1348 KB Output is correct
2 Correct 336 ms 1620 KB Output is correct
3 Incorrect 318 ms 1492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2596 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -