oj.uz

Submission #681915

# Submission time Handle Problem Language Result Execution time Memory
681915 2023-01-14T21:04:20 Z Kahou Park (BOI16_park) C++14
100 / 100
 462 ms 66192 KB 
#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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 63256 KB Output is correct
2 Correct 389 ms 63260 KB Output is correct
3 Correct 394 ms 63260 KB Output is correct
4 Correct 397 ms 63260 KB Output is correct
5 Correct 390 ms 63260 KB Output is correct
6 Correct 393 ms 63256 KB Output is correct
7 Correct 364 ms 63332 KB Output is correct
8 Correct 376 ms 63260 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 3916 KB Output is correct
2 Correct 37 ms 3884 KB Output is correct
3 Correct 40 ms 3800 KB Output is correct
4 Correct 39 ms 3932 KB Output is correct
5 Correct 45 ms 3868 KB Output is correct
6 Correct 36 ms 3936 KB Output is correct
7 Correct 34 ms 3356 KB Output is correct
8 Correct 34 ms 3300 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 63256 KB Output is correct
2 Correct 389 ms 63260 KB Output is correct
3 Correct 394 ms 63260 KB Output is correct
4 Correct 397 ms 63260 KB Output is correct
5 Correct 390 ms 63260 KB Output is correct
6 Correct 393 ms 63256 KB Output is correct
7 Correct 364 ms 63332 KB Output is correct
8 Correct 376 ms 63260 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 39 ms 3916 KB Output is correct
12 Correct 37 ms 3884 KB Output is correct
13 Correct 40 ms 3800 KB Output is correct
14 Correct 39 ms 3932 KB Output is correct
15 Correct 45 ms 3868 KB Output is correct
16 Correct 36 ms 3936 KB Output is correct
17 Correct 34 ms 3356 KB Output is correct
18 Correct 34 ms 3300 KB Output is correct
19 Correct 426 ms 66176 KB Output is correct
20 Correct 452 ms 66040 KB Output is correct
21 Correct 427 ms 66128 KB Output is correct
22 Correct 462 ms 66044 KB Output is correct
23 Correct 431 ms 66032 KB Output is correct
24 Correct 400 ms 66192 KB Output is correct