oj.uz

Submission #484687

# Submission time Handle Problem Language Result Execution time Memory
484687 2021-11-05T04:17:45 Z minhcool Park (BOI16_park) C++17
100 / 100
 912 ms 52308 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>

using namespace std;
typedef long long int Z;

Z T, P;
Z xm, ym;
Z tx[5050];
Z ty[5050];
Z tr[5050];

Z par[5050];

Z find(Z x) {
	if(par[par[x]] != par[x]) {
		par[x] = find(par[x]);
	}
	return par[x];
}

void merge(Z a, Z b) {
	a = find(a);
	b = find(b);
	par[a] = b;
}

// Trees T, T + 1, T + 2, T + 3 are the bottom, right, top and left borders.
bool overlap(Z time, Z tree1, Z tree2) {
	if(tree1 >= T) {
		if(tree2 >= T) {
			return false;
		} else {
			if(tree1 == T    ) return ty[tree2] - tr[tree2] - time < time;
			if(tree1 == T + 1) return tx[tree2] + tr[tree2] + time > xm - time;
			if(tree1 == T + 2) return ty[tree2] + tr[tree2] + time > ym - time;
			if(tree1 == T + 3) return tx[tree2] - tr[tree2] - time < time;
			throw 5;
			return false;
		}
	} else {
		if(tree2 >= T) {
			return overlap(time, tree2, tree1);
		} else {
			Z dx = tx[tree1] - tx[tree2];
			Z dy = ty[tree1] - ty[tree2];
			Z dist2 = dx * dx + dy * dy;
			Z maxdist2 = tr[tree1] + tr[tree2] + 2 * time;
			maxdist2 *= maxdist2;
			return dist2 < maxdist2;
		}
	}
}

int main() {
	for(Z i = 0; i < 5050; ++i) par[i] = i;
	
	cin.sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> T >> P;
	cin >> xm >> ym;
	
	for(Z t = 0; t < T; ++t) {
		cin >> tx[t] >> ty[t] >> tr[t];
	}
	
	// ((radius, corner), order)
	vector<pair<pair<Z, Z>, Z>> Q(P);
	for(Z p = 0; p < P; ++p) {
		cin >> Q[p].first.first >> Q[p].first.second;
		--Q[p].first.second;
		Q[p].second = p;
	}
	sort(Q.begin(), Q.end());
	
	// (time, (tree1, tree2))
	vector<pair<Z, pair<Z, Z>>> events;
	for(Z i = 0; i < T + 4; ++i) {
		for(Z j = i + 1; j < T + 4; ++j) {
			Z A = 0;
			Z B = xm + ym + 5;
			while(A != B) {
				Z M = (A + B) / 2;
				if(overlap(M, i, j)) {
					B = M;
				} else {
					A = M + 1;
				}
			}
			events.emplace_back(A, make_pair(i, j));
		}
	}
	sort(events.begin(), events.end());
	
	vector<array<bool, 4>> res(P);
	Z evi = 0;
	for(auto q : Q) {
		while(evi != (Z)events.size() && events[evi].first <= q.first.first) {
			merge(events[evi].second.first, events[evi].second.second);
			++evi;
		}
		Z c = q.first.second;
		array<bool, 4>& r = res[q.second];
		auto conn = [c](Z a, Z b) {
			return find(T + (c + a) % 4) == find(T + (c + b) % 4);
		};
		r[c] = true;
		if(!conn(0, 1) && !conn(0, 2) && !conn(0, 3)) r[(c + 1) % 4] = true;
		if(!conn(0, 2) && !conn(0, 3) && !conn(1, 2) && !conn(1, 3)) r[(c + 2) % 4] = true;
		if(!conn(3, 0) && !conn(3, 1) && !conn(3, 2)) r[(c + 3) % 4] = true;
	}
	for(array<bool, 4> r : res) {
		for(Z i = 0; i < 4; ++i) {
			if(r[i]) {
				cout << i + 1;
			}
		}
		cout << '\n';
	}
	
	return 0;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 802 ms 49740 KB Output is correct
2 Correct 814 ms 49740 KB Output is correct
3 Correct 843 ms 49824 KB Output is correct
4 Correct 837 ms 49800 KB Output is correct
5 Correct 841 ms 49668 KB Output is correct
6 Correct 819 ms 49924 KB Output is correct
7 Correct 759 ms 49784 KB Output is correct
8 Correct 774 ms 49696 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 4004 KB Output is correct
2 Correct 50 ms 4000 KB Output is correct
3 Correct 48 ms 3984 KB Output is correct
4 Correct 45 ms 3996 KB Output is correct
5 Correct 51 ms 4004 KB Output is correct
6 Correct 53 ms 4116 KB Output is correct
7 Correct 42 ms 3396 KB Output is correct
8 Correct 39 ms 3396 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 802 ms 49740 KB Output is correct
2 Correct 814 ms 49740 KB Output is correct
3 Correct 843 ms 49824 KB Output is correct
4 Correct 837 ms 49800 KB Output is correct
5 Correct 841 ms 49668 KB Output is correct
6 Correct 819 ms 49924 KB Output is correct
7 Correct 759 ms 49784 KB Output is correct
8 Correct 774 ms 49696 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 50 ms 4004 KB Output is correct
12 Correct 50 ms 4000 KB Output is correct
13 Correct 48 ms 3984 KB Output is correct
14 Correct 45 ms 3996 KB Output is correct
15 Correct 51 ms 4004 KB Output is correct
16 Correct 53 ms 4116 KB Output is correct
17 Correct 42 ms 3396 KB Output is correct
18 Correct 39 ms 3396 KB Output is correct
19 Correct 883 ms 52020 KB Output is correct
20 Correct 855 ms 52224 KB Output is correct
21 Correct 912 ms 52088 KB Output is correct
22 Correct 866 ms 52308 KB Output is correct
23 Correct 912 ms 52156 KB Output is correct
24 Correct 897 ms 52080 KB Output is correct