oj.uz

Submission #535604

# Submission time Handle Problem Language Result Execution time Memory
535604 2022-03-10T16:27:47 Z new_acc Park (BOI16_park) C++14
0 / 100
 1165 ms 16152 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<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.0

# Verdict Execution time Memory Grader output
1 Correct 665 ms 16096 KB Output is correct
2 Correct 676 ms 16084 KB Output is correct
3 Correct 697 ms 16080 KB Output is correct
4 Correct 626 ms 16112 KB Output is correct
5 Correct 658 ms 16084 KB Output is correct
6 Correct 659 ms 16084 KB Output is correct
7 Correct 1149 ms 16148 KB Output is correct
8 Correct 1165 ms 16152 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Incorrect 0 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1684 KB Output is correct
2 Correct 34 ms 1552 KB Output is correct
3 Incorrect 36 ms 1476 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 665 ms 16096 KB Output is correct
2 Correct 676 ms 16084 KB Output is correct
3 Correct 697 ms 16080 KB Output is correct
4 Correct 626 ms 16112 KB Output is correct
5 Correct 658 ms 16084 KB Output is correct
6 Correct 659 ms 16084 KB Output is correct
7 Correct 1149 ms 16148 KB Output is correct
8 Correct 1165 ms 16152 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Incorrect 0 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -