oj.uz

답안 #21001

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
21001 2017-03-27T10:58:20 Z model_code Park (BOI16_park) C++11
100 / 100
 1153 ms 78340 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 >> 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;
}

Compilation message

Subtask #1
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1103 ms 75996 KB Output is correct
2 Correct 1106 ms 75996 KB Output is correct
3 Correct 1043 ms 75996 KB Output is correct
4 Correct 1079 ms 75996 KB Output is correct
5 Correct 1083 ms 75996 KB Output is correct
6 Correct 1018 ms 75996 KB Output is correct
7 Correct 986 ms 75996 KB Output is correct
8 Correct 993 ms 75996 KB Output is correct
9 Correct 0 ms 2184 KB Output is correct
10 Correct 0 ms 2184 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 5768 KB Output is correct
2 Correct 113 ms 5768 KB Output is correct
3 Correct 103 ms 5768 KB Output is correct
4 Correct 99 ms 5768 KB Output is correct
5 Correct 106 ms 5768 KB Output is correct
6 Correct 103 ms 5768 KB Output is correct
7 Correct 93 ms 4920 KB Output is correct
8 Correct 109 ms 4920 KB Output is correct

Subtask #3
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1103 ms 75996 KB Output is correct
2 Correct 1106 ms 75996 KB Output is correct
3 Correct 1043 ms 75996 KB Output is correct
4 Correct 1079 ms 75996 KB Output is correct
5 Correct 1083 ms 75996 KB Output is correct
6 Correct 1018 ms 75996 KB Output is correct
7 Correct 986 ms 75996 KB Output is correct
8 Correct 993 ms 75996 KB Output is correct
9 Correct 0 ms 2184 KB Output is correct
10 Correct 0 ms 2184 KB Output is correct
11 Correct 113 ms 5768 KB Output is correct
12 Correct 113 ms 5768 KB Output is correct
13 Correct 103 ms 5768 KB Output is correct
14 Correct 99 ms 5768 KB Output is correct
15 Correct 106 ms 5768 KB Output is correct
16 Correct 103 ms 5768 KB Output is correct
17 Correct 93 ms 4920 KB Output is correct
18 Correct 109 ms 4920 KB Output is correct
19 Correct 1119 ms 78340 KB Output is correct
20 Correct 1089 ms 78340 KB Output is correct
21 Correct 1139 ms 78340 KB Output is correct
22 Correct 1136 ms 78340 KB Output is correct
23 Correct 1153 ms 78340 KB Output is correct
24 Correct 1129 ms 78340 KB Output is correct