oj.uz

Submission #932680

# Submission time Handle Problem Language Result Execution time Memory
932680 2024-02-24T03:00:45 Z Angus_Yeung Park (BOI16_park) C++14
27 / 100
 342 ms 73248 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;
	long double dis;
	dista(ll id1, ll id2, long double 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];

long double f(ll i, ll j) {
	return 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;
	cin >> w >> h;
	
	p[n+1] = n+1;
	p[n+2] = n+2;
	p[n+3] = n+3;
	p[n+4] = n+4;
	for (int i = 1; i <= n; i++) {
		p[i] = 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));
	}
	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 342 ms 72640 KB Output is correct
2 Correct 336 ms 72884 KB Output is correct
3 Correct 324 ms 71848 KB Output is correct
4 Correct 323 ms 73248 KB Output is correct
5 Correct 324 ms 72644 KB Output is correct
6 Correct 325 ms 72364 KB Output is correct
7 Correct 320 ms 72644 KB Output is correct
8 Correct 304 ms 72896 KB Output is correct
9 Correct 2 ms 5720 KB Output is correct
10 Correct 2 ms 5724 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 6872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 72640 KB Output is correct
2 Correct 336 ms 72884 KB Output is correct
3 Correct 324 ms 71848 KB Output is correct
4 Correct 323 ms 73248 KB Output is correct
5 Correct 324 ms 72644 KB Output is correct
6 Correct 325 ms 72364 KB Output is correct
7 Correct 320 ms 72644 KB Output is correct
8 Correct 304 ms 72896 KB Output is correct
9 Correct 2 ms 5720 KB Output is correct
10 Correct 2 ms 5724 KB Output is correct
11 Incorrect 89 ms 6872 KB Output isn't correct
12 Halted 0 ms 0 KB -