Submission #681915

#	Time	Username	Problem	Language	Result	Execution time	Memory
681915		Kahou	Park (BOI16_park)	C++14	100 / 100	462 ms	66192 KiB

park

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 2050, M = 1e5 + 50, X = 5e6 + 50;
const long double eps = 1e-6;
int n, m, w, h, pr[N], sz[N];
pair<pii, int> B[N], A[M];
pair<long double, pii> E[X];
bool out[M][4];

int getroot(int u) {
	if (pr[u] == u) return u;
	return pr[u] = getroot(pr[u]);
}
void uniset(int u, int v) {
	u = getroot(u), v = getroot(v);
	if (u == v) return;
	if (sz[u] < sz[v]) swap(u,v);
	pr[v] = u;
	sz[u] += sz[v];
}
void solve() {
	cin >> n >> m;
	cin >> w >> h;
	for (int i = 1; i <= n; i++) {
		int x, y, r;
		cin >> x >> y >> r;
		B[i] = {{x, y}, r};
	}
	for (int u = 1; u <= n+4; u++) {
		pr[u] = u;
		sz[u] = 1;
	}

	int t = 0;
	for (int u = 1; u <= n; u++) {
		int x = B[u].F.F, y = B[u].F.S;
		int r = B[u].S;
		E[++t] = {x-r, {u, n+1}};
		E[++t] = {y-r, {u, n+4}};
		E[++t] = {w-x-r, {u, n+3}};
		E[++t] = {h-y-r, {u, n+2}};

		for (int v = u+1; v <= n; v++) {
			int xp = B[v].F.F, yp = B[v].F.S;
			int rp = B[v].S;
			double dis = 1.0*sqrt(1.0*(x-xp)*(x-xp)+1.0*(y-yp)*(y-yp))-r-rp;
			E[++t] = {dis, {u, v}};
		}
	}
	for (int i = 1; i <= m; i++) {
		int r, e;
		cin >> r >> e;
		A[i] = {{r, e}, i};
	}
	sort(A+1, A+m+1);
	sort(E+1, E+t+1);
	int pt = 1;
	
	for (int i = 1; i <= t; i++) {
		while (pt <= m && 2*A[pt].F.F <= E[i].F+eps) {
			int x = A[pt].F.S-1;
			int id = A[pt].S;
			for (int c = 0; c < 4; c++) {
				out[id][c] = 1;
			}
			for (int u = n+1; u <= n+4; u++) {
				for (int v = u+1; v <= n+4; v++) {
					if (getroot(u) != getroot(v)) continue;
					if (u == n+1) {
						if (v == n+2) {
							if (x == 3) out[id][0] = out[id][1] = out[id][2] = 0;
							else out[id][3] = 0;
						}
						if (v == n+3) {
							if (x == 2 || x == 3) out[id][0] = out[id][1] = 0;
							else out[id][2] = out[id][3] = 0;
						}
						if (v == n+4) {
							if (x == 0) out[id][1] = out[id][2] = out[id][3] = 0;
							else out[id][0] = 0;
						}
					}
					if (u == n+2) {
						if (v == n+3) {
							if (x == 2) out[id][0] = out[id][1] = out[id][3] = 0;
							else out[id][2] = 0;
						}
						if (v == n+4) {
							if (x == 2 || x == 1) out[id][0] = out[id][3] = 0;
							else out[id][1] = out[id][2] = 0;
						}
					}
					if (u == n+3) {
						if (v == n+4) {
							if (x == 1) out[id][2] = out[id][0] = out[id][3] = 0;
							else out[id][1] = 0;
						}
					}
				}
			}
			pt++;
		}
		uniset(E[i].S.F, E[i].S.S);
	}
	for (int i = 1; i <= m; i++) {
		int ans = 0;
		for (int c = 0; c < 4; c++) {
			if (out[i][c]) ans = ans*10+c+1;
		}
		cout << ans << endl;
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	solve();
	return 0;
}

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