Submission #383261

#	Time	Username	Problem	Language	Result	Execution time	Memory
383261		ngpin04	Park (BOI16_park)	C++14	100 / 100	462 ms	25768 KiB

park

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 2e3 + 10;

pair <int, int> a[N];

vector <pair <int, pair <int, int> > > edge;

int ans[5][5];
int par[N];
int r[N];
int n,m,w,h;

int dis(int i, int j) {
	int dx = (a[i].fi - a[j].fi);
	int dy = (a[i].se - a[j].se);
	return sqrt((long long) dx * dx + (long long) dy * dy);
}

int getpar(int u) {
	return (par[u] < 0) ? u : (par[u] = getpar(par[u]));
}

void join(int u, int v) {
	u = getpar(u);
	v = getpar(v);
	if (u == v)
		return;
	if (par[u] > par[v])
		swap(u, v);
	par[u] += par[v];
	par[v] = u;	
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> w >> h;
	for (int i = 1; i <= n; i++)
		cin >> a[i].fi >> a[i].se >> r[i];
 	
	for (int i = 1; i <= 4; i++)
	for (int j = 1; j <= 4; j++)
		ans[i][j] = 1e9 + 1;

	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			int len = (dis(i, j) - r[i] - r[j]) >> 1;
			edge.push_back(mp(len, mp(i, j)));
		}

		edge.push_back(mp((a[i].fi - r[i]) >> 1, mp(i, n + 1)));
		edge.push_back(mp((a[i].se - r[i]) >> 1, mp(i, n + 2)));
		edge.push_back(mp((w - a[i].fi - r[i]) >> 1, mp(i, n + 3)));
		edge.push_back(mp((h - a[i].se - r[i]) >> 1, mp(i, n + 4)));
	}
	sort(edge.begin(), edge.end());

	for (int i = 1; i <= n + 4; i++)
		par[i] = -1;

	for (auto e : edge) {
		int u = e.se.fi;
		int v = e.se.se;
		int w = e.fi;
		join(u, v);

		for (int i = 1; i <= 4; i++) {
			int j = i % 4 + 1;
			if (getpar(n + i) == getpar(n + j)) {
				for (int k = 1; k <= 4; k++) 
					if (i != k)
						ans[i][k] = ans[k][i] = min(ans[i][k], w);
			}
		}

		if (getpar(n + 1) == getpar(n + 3)) {
			for (int i : {1, 2})
				for (int j : {3, 4})
					ans[i][j] = ans[j][i] = min(ans[i][j], w);
		}

		if (getpar(n + 2) == getpar(n + 4)) {
			for (int i : {1, 4})
				for (int j : {2, 3}) 
					ans[i][j] = ans[j][i] = min(ans[i][j], w);
		}
	}
	while (m--) {
		int r,e; cin >> r >> e;
		for (int i = 1; i <= 4; i++)
			if (r <= ans[e][i])
				cout << i;
		cout << "\n";
	}

	return 0;
}

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