Submission #484679

#	Time	Username	Problem	Language	Result	Execution time	Memory
484679		minhcool	Park (BOI16_park)	C++17	0 / 100	1828 ms	73564 KiB

park

/*
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
*/
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 2011;

const int oo = 1e18 + 7, mod = 1e9 + 7;

int n, q, w, h;
long double x[N], y[N], r[N];

long double need[N][N];

vector<int> Adj[N];

bool vis[N];

long double req[N][N];

bool ck(int u, int v, long double z){
	for(int i = 1; i <= n + 4; i++) Adj[i].clear();
	for(int i = 1; i <= n; i++){
		for(int j = i + 1; j <= n; j++){
			if(need[i][j] <= z){
				Adj[i].pb(j);
				Adj[j].pb(i);
			}
		}
	}
	for(int i = 1; i <= n; i++){
		if(x[i] <= (r[i] + z)){
			Adj[i].pb(n + 1);
			Adj[n + 1].pb(i);
		}
	}
	for(int i = 1; i <= n; i++){
		if(y[i] >= (h - r[i] - z)){
			Adj[i].pb(n + 2);
			Adj[n + 2].pb(i);
		}
	}
	for(int i = 1; i <= n; i++){
		if(x[i] >= (w - r[i] - z)){
			Adj[i].pb(n + 3);
			Adj[n + 3].pb(i);
		}
	}
	for(int i = 1; i <= n; i++){
		if(y[i] <= (r[i] + z)){
			Adj[i].pb(n + 4);
			Adj[n + 4].pb(i);
		}
	}
	/*
	cout << z << "\n";
	for(auto it : Adj[n + 1]) cout << it << " ";
	cout << "\n";
	for(auto it : Adj[n + 2]) cout << it << " ";
	cout << "\n";
	for(auto it : Adj[n + 3]) cout << it << " ";
	cout << "\n";
	for(auto it : Adj[n + 4]) cout << it << " ";
	cout << "\n";
	*/
	queue<int> bfs;
	for(int i = 1; i <= n + 4; i++) vis[i] = 0;
	vis[u] = 1;	
	bfs.push(u);
	while(!bfs.empty()){
		int x = bfs.front();
		//if(u == 7 && v == 8) cout << z << " " << u << " " << x << "\n";
		bfs.pop();
		for(auto y : Adj[x]){
			if(vis[y]) continue;
			vis[y] = 1;
			bfs.push(y);
		}
	}
	return (vis[v] == 1);
}

int temp[5];

void process(){
	temp[1] = 1, temp[2] = 4, temp[3] = 3, temp[4] = 2;
	cin >> n >> q;
	cin >> w >> h;
	for(int i = 1; i <= n; i++){
		cin >> x[i] >> y[i] >> r[i];
	}
	for(int i = 1; i <= n; i++){
		for(int j = i + 1; j <= n; j++){
			int temp = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
			need[i][j] = sqrt((long double)temp);
			need[i][j] -= r[i] + r[j];
			need[i][j] = max(need[i][j], (long double)0.0);
			need[i][j] /= 2.0;
		}
	}
	for(int i = n + 1; i <= n + 4; i++){
		for(int j = i + 1; j <= n + 4; j++){
			long double l = 0, r = max(w, h);
			while((r - l) >= 0.1){
				long double mid = (l + r) / 2.0;
				if(!ck(i, j, mid)) l = mid;
				else r = mid;
			}
			//cout << i << " " << j << " " << l << "\n";
			req[i][j] = req[j][i] = l;
		}
	}
	while(q--){
		long double r;
		int k;
		cin >> r >> k;
		for(int i = 1; i <= 4; i++){
			if(k == i){cout << i;}
			else{
				bool ck = 1;
				if((((i - 1) / 2) != ((k - 1) / 2)) && req[n + 1][n + 3] < r) ck = 0;
				if((i + k) != 5 && req[n + 2][n + 4] < r) ck = 0; 
				//cout << k << " " << i << " " << ck << "\n";
				if(req[n + temp[i]][n + ((temp[i] + 2) % 4) + 1] < r) ck = 0;
				//cout << k << " " << i << " " << req[n + i][n + ((i + 2) % 4) + 1] << " " << ck << "\n";
				if(req[n + temp[k]][n + ((temp[k] + 2) % 4) + 1] < r) ck = 0;
				//cout << i << " " << ((i + 2) % 4) + 1 << "\n";
				if(ck) cout << i;
			}
		}
		cout << "\n";
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
	process();
}

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