oj.uz

Submission #349446

# Submission time Handle Problem Language Result Execution time Memory
349446 2021-01-17T15:43:28 Z mp007mp Park (BOI16_park) C++14
58 / 100
 326 ms 876 KB 
#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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 492 KB Output is correct
2 Correct 13 ms 492 KB Output is correct
3 Correct 4 ms 492 KB Output is correct
4 Correct 9 ms 492 KB Output is correct
5 Correct 3 ms 492 KB Output is correct
6 Correct 6 ms 492 KB Output is correct
7 Correct 21 ms 620 KB Output is correct
8 Correct 14 ms 620 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 768 KB Output is correct
2 Correct 70 ms 760 KB Output is correct
3 Correct 55 ms 748 KB Output is correct
4 Correct 64 ms 748 KB Output is correct
5 Correct 56 ms 748 KB Output is correct
6 Correct 65 ms 748 KB Output is correct
7 Correct 34 ms 748 KB Output is correct
8 Correct 36 ms 748 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 492 KB Output is correct
2 Correct 13 ms 492 KB Output is correct
3 Correct 4 ms 492 KB Output is correct
4 Correct 9 ms 492 KB Output is correct
5 Correct 3 ms 492 KB Output is correct
6 Correct 6 ms 492 KB Output is correct
7 Correct 21 ms 620 KB Output is correct
8 Correct 14 ms 620 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 62 ms 768 KB Output is correct
12 Correct 70 ms 760 KB Output is correct
13 Correct 55 ms 748 KB Output is correct
14 Correct 64 ms 748 KB Output is correct
15 Correct 56 ms 748 KB Output is correct
16 Correct 65 ms 748 KB Output is correct
17 Correct 34 ms 748 KB Output is correct
18 Correct 36 ms 748 KB Output is correct
19 Incorrect 326 ms 876 KB Output isn't correct
20 Halted 0 ms 0 KB -