oj.uz

Submission #383261

# Submission time Handle Problem Language Result Execution time Memory
383261 2021-03-29T11:15:47 Z ngpin04 Park (BOI16_park) C++14
100 / 100
 462 ms 25768 KB 
#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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 25164 KB Output is correct
2 Correct 422 ms 25172 KB Output is correct
3 Correct 417 ms 25172 KB Output is correct
4 Correct 419 ms 25172 KB Output is correct
5 Correct 420 ms 25164 KB Output is correct
6 Correct 417 ms 25164 KB Output is correct
7 Correct 365 ms 25172 KB Output is correct
8 Correct 339 ms 25172 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 42 ms 1104 KB Output is correct
2 Correct 40 ms 2152 KB Output is correct
3 Correct 39 ms 2024 KB Output is correct
4 Correct 39 ms 2152 KB Output is correct
5 Correct 40 ms 2152 KB Output is correct
6 Correct 44 ms 2152 KB Output is correct
7 Correct 34 ms 1920 KB Output is correct
8 Correct 34 ms 1900 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 25164 KB Output is correct
2 Correct 422 ms 25172 KB Output is correct
3 Correct 417 ms 25172 KB Output is correct
4 Correct 419 ms 25172 KB Output is correct
5 Correct 420 ms 25164 KB Output is correct
6 Correct 417 ms 25164 KB Output is correct
7 Correct 365 ms 25172 KB Output is correct
8 Correct 339 ms 25172 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 42 ms 1104 KB Output is correct
12 Correct 40 ms 2152 KB Output is correct
13 Correct 39 ms 2024 KB Output is correct
14 Correct 39 ms 2152 KB Output is correct
15 Correct 40 ms 2152 KB Output is correct
16 Correct 44 ms 2152 KB Output is correct
17 Correct 34 ms 1920 KB Output is correct
18 Correct 34 ms 1900 KB Output is correct
19 Correct 462 ms 25768 KB Output is correct
20 Correct 461 ms 25636 KB Output is correct
21 Correct 453 ms 25636 KB Output is correct
22 Correct 459 ms 25508 KB Output is correct
23 Correct 453 ms 25508 KB Output is correct
24 Correct 379 ms 25636 KB Output is correct