oj.uz

Submission #932682

# Submission time Handle Problem Language Result Execution time Memory
932682 2024-02-24T03:09:04 Z Angus_Yeung Park (BOI16_park) C++14
100 / 100
 286 ms 57276 KB 
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<ll, ll>
typedef long long ll;
const ll MOD = 1000000007LL;
const ll INF = 1e15;
using namespace std;

struct tree {
	ll x, y, r;
};

struct visitor {
	ll e, r, id;
	string ans;
};

struct dista {
	ll id1, id2, dis;
	dista(ll id1, ll id2, ll dis): id1(id1), id2(id2), dis(dis) {}
};

ll n, m, w, h, p[2020];
tree a[2010];
visitor b[100010];
vector<dista> v;
bool tmp[10][10];

ll f(ll i, ll j) {
	return floor(sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)))-a[i].r-a[j].r;
}

ll find(ll x) {
	if (p[x] == x) return x;
	return p[x] = find(p[x]);
}

int main() {
	cin.tie(0); cout.tie(0);
	ios::sync_with_stdio(0);
	
	cin >> n >> m >> w >> h;
	
	for (int i = 1; i <= 4; i++) p[n+i] = n+i;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].x >> a[i].y >> a[i].r;
		for (int j = 1; j < i; j++) {
			v.push_back(dista(j, i, f(i, j)));
		}
		v.push_back(dista(i, n+1, a[i].y-a[i].r));
		v.push_back(dista(i, n+2, w-a[i].x-a[i].r));
		v.push_back(dista(i, n+3, h-a[i].y-a[i].r));
		v.push_back(dista(i, n+4, a[i].x-a[i].r));
		p[i] = i;
	}
	sort(v.begin(), v.end(), [&](dista x, dista y) -> bool {
		return x.dis > y.dis;
	});
	
	for (int i = 1; i <= m; i++) {
		cin >> b[i].r >> b[i].e;
		b[i].id = i;
	}
	sort(b+1, b+m+1, [&](visitor x, visitor y) -> bool {
		return x.r < y.r;
	});
	
	for (int i = 1; i <= m; i++) {
		while (!v.empty() && v.back().dis < 2*b[i].r) {
			p[find(v.back().id1)] = p[find(v.back().id2)];
			v.pop_back();
		}
		for (int j = 0; j <= 15; j++) {
			tmp[j/4+1][j%4+1] = 1;
		}
		for (int j = 1; j <= 4; j++) {
			ll xx = j, yy = j%4+1;
			if (find(n+xx) != find(n+yy)) continue;
			for (int k = 1; k <= 4; k++) {
				if (k == yy) continue;
				tmp[k][yy] = tmp[yy][k] = 0;
			}
		}
		if (find(n+1) == find(n+3)) {
			tmp[1][2] = tmp[1][3] = tmp[2][1] = tmp[3][1] = 0;
			tmp[4][2] = tmp[4][3] = tmp[2][4] = tmp[3][4] = 0;
		}
		if (find(n+2) == find(n+4)) {
			tmp[1][4] = tmp[1][3] = tmp[4][1] = tmp[3][1] = 0;
			tmp[4][2] = tmp[2][3] = tmp[2][4] = tmp[3][2] = 0;
		}
		b[i].ans = "";
		for (int j = 1; j <= 4; j++) {
			if (tmp[b[i].e][j]) b[i].ans += '0'+j;
		}
	}
	sort(b+1, b+m+1, [&](visitor x, visitor y) -> bool {
		return x.id < y.id;
	});
	
	for (int i = 1; i <= m; i++) cout << b[i].ans << "\n";
	
	return 0;
}
/*

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

*/

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 56052 KB Output is correct
2 Correct 195 ms 56300 KB Output is correct
3 Correct 194 ms 56252 KB Output is correct
4 Correct 195 ms 55488 KB Output is correct
5 Correct 192 ms 56000 KB Output is correct
6 Correct 197 ms 55708 KB Output is correct
7 Correct 191 ms 56756 KB Output is correct
8 Correct 185 ms 57276 KB Output is correct
9 Correct 1 ms 5724 KB Output is correct
10 Correct 1 ms 5704 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 6856 KB Output is correct
2 Correct 91 ms 7872 KB Output is correct
3 Correct 98 ms 7816 KB Output is correct
4 Correct 94 ms 8140 KB Output is correct
5 Correct 91 ms 7880 KB Output is correct
6 Correct 89 ms 7880 KB Output is correct
7 Correct 88 ms 7360 KB Output is correct
8 Correct 87 ms 7248 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 56052 KB Output is correct
2 Correct 195 ms 56300 KB Output is correct
3 Correct 194 ms 56252 KB Output is correct
4 Correct 195 ms 55488 KB Output is correct
5 Correct 192 ms 56000 KB Output is correct
6 Correct 197 ms 55708 KB Output is correct
7 Correct 191 ms 56756 KB Output is correct
8 Correct 185 ms 57276 KB Output is correct
9 Correct 1 ms 5724 KB Output is correct
10 Correct 1 ms 5704 KB Output is correct
11 Correct 91 ms 6856 KB Output is correct
12 Correct 91 ms 7872 KB Output is correct
13 Correct 98 ms 7816 KB Output is correct
14 Correct 94 ms 8140 KB Output is correct
15 Correct 91 ms 7880 KB Output is correct
16 Correct 89 ms 7880 KB Output is correct
17 Correct 88 ms 7360 KB Output is correct
18 Correct 87 ms 7248 KB Output is correct
19 Correct 286 ms 55736 KB Output is correct
20 Correct 282 ms 56244 KB Output is correct
21 Correct 286 ms 56744 KB Output is correct
22 Correct 278 ms 56240 KB Output is correct
23 Correct 283 ms 56244 KB Output is correct
24 Correct 273 ms 55744 KB Output is correct