oj.uz

Submission #350892

# Submission time Handle Problem Language Result Execution time Memory
350892 2021-01-19T09:41:12 Z saniyar_krmi Park (BOI16_park) C++14
100 / 100
 657 ms 243608 KB 
// YOU ONLY GOT ONE SHOT
#include <bits/stdc++.h>
#define put(x) cerr << #x << ": " << x << '\n'
#define line() cerr << "**************\n"
#pragma GCC optimize ("Ofast")
 
#define F first
#define S second
//#define mul(x, y) (((x) * (y)) %mod)
//#define bit(i, j) (((i)>>(j)) &1)
//#define left(id) ((id<<1) + 1)
//#define right(id) ((id<<1) + 2)
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
 
const int maxn = 5e6 + 10;
 
int n, m, w, h;
vector <pair<double, pii>> all;
double tx[maxn], ty[maxn], tr[maxn];
 
int p[maxn];
 
string ans[maxn];
 
int get(int a){
	return p[a] = (p[a] == a ? a : get(p[a]));
}
 
bool same(int a, int b){
	return get(a) == get(b);
}
 
void unite(int a, int b){
	a = get(a), b = get(b);
	if(a == b)
		return;
	p[b] = a;
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);  cout.tie(0);
 
	for(int i=0; i<maxn; i++) p[i] = i;
 
	cin >> n >> m >> w >> h;
	for(int i=0; i<n; i++){
		cin >> tx[i] >> ty[i] >> tr[i];
		for(int j=0; j<i; j++){
			double d = hypot(abs(tx[i] - tx[j]), abs(ty[i] - ty[j])) - tr[i] - tr[j];
			all.push_back({d, {i, j}});
		}
		all.push_back({ty[i] - tr[i], {i, n+1}});
		all.push_back({tx[i] - tr[i], {i, n+2}});
		all.push_back({w - tx[i] - tr[i], {i, n+3}});
		all.push_back({h - ty[i] - tr[i], {i, n+4}});
	}
 
	double r;
	int e;
	for(int i=1; i<=m; i++){
		cin >> r >> e;
		all.push_back({r*2, {-i, e}});
	}
	sort(all.begin(), all.end());
 
	for(auto a: all){
		if(a.S.F < 0){
			int j = -(a.S.F + 1);
			int e = a.S.S;
			if(same(n + 1, n + 4) && same(n + 2, n + 3)){
				ans[j] = char('0' + e);
			}
			else if(same(n + 1, n + 4)){
				if(e == 1 || e == 4){
					if(!same(n + 1, n + 2) && !same(n + 2, n + 4))
						ans[j] = "14";
					else
						ans[j] = char('0' + e);
				}
				else{
					if(!same(n + 1, n + 3) && !same(n + 3, n + 4))
						ans[j] = "23";
					else
						ans[j] = char('0' + e);
				}
			}
			else if(same(n + 2, n + 3)){
				if(e == 1 || e == 2){
					if(!same(n + 1, n + 2) && !same(n + 1, n + 3))
						ans[j] = "12";
					else
						ans[j] = char('0' + e);
				}
				else{
					if(!same(n + 2, n + 4) && !same(n + 3, n + 4))
						ans[j] = "34";
					else
						ans[j] = char('0' + e);
				}
			}
			else{
				vector <int> ok(5, 1);
				if(same(n + 1, n + 2)) ok[1] = 0;
				if(same(n + 1, n + 3)) ok[2] = 0;
				if(same(n + 3, n + 4)) ok[3] = 0;
				if(same(n + 2, n + 4)) ok[4] = 0;
 
				for(int k=1; k<=4; k++)
					if((ok[e] && ok[k]) || e == k)
						ans[j] += char('0' + k);
			}
		}
		else{
			unite(a.S.F, a.S.S);
		}
	}
 
	for(int i=0; i<m; i++)
		cout << ans[i] << '\n';
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 209536 KB Output is correct
2 Correct 520 ms 209468 KB Output is correct
3 Correct 525 ms 209468 KB Output is correct
4 Correct 561 ms 209616 KB Output is correct
5 Correct 530 ms 209468 KB Output is correct
6 Correct 538 ms 209468 KB Output is correct
7 Correct 459 ms 209608 KB Output is correct
8 Correct 479 ms 209468 KB Output is correct
9 Correct 116 ms 176492 KB Output is correct
10 Correct 113 ms 176492 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 178916 KB Output is correct
2 Correct 200 ms 178916 KB Output is correct
3 Correct 215 ms 178916 KB Output is correct
4 Correct 191 ms 178916 KB Output is correct
5 Correct 216 ms 178848 KB Output is correct
6 Correct 191 ms 179044 KB Output is correct
7 Correct 196 ms 178792 KB Output is correct
8 Correct 188 ms 178824 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 209536 KB Output is correct
2 Correct 520 ms 209468 KB Output is correct
3 Correct 525 ms 209468 KB Output is correct
4 Correct 561 ms 209616 KB Output is correct
5 Correct 530 ms 209468 KB Output is correct
6 Correct 538 ms 209468 KB Output is correct
7 Correct 459 ms 209608 KB Output is correct
8 Correct 479 ms 209468 KB Output is correct
9 Correct 116 ms 176492 KB Output is correct
10 Correct 113 ms 176492 KB Output is correct
11 Correct 194 ms 178916 KB Output is correct
12 Correct 200 ms 178916 KB Output is correct
13 Correct 215 ms 178916 KB Output is correct
14 Correct 191 ms 178916 KB Output is correct
15 Correct 216 ms 178848 KB Output is correct
16 Correct 191 ms 179044 KB Output is correct
17 Correct 196 ms 178792 KB Output is correct
18 Correct 188 ms 178824 KB Output is correct
19 Correct 623 ms 243480 KB Output is correct
20 Correct 657 ms 243480 KB Output is correct
21 Correct 640 ms 243352 KB Output is correct
22 Correct 605 ms 243352 KB Output is correct
23 Correct 606 ms 243352 KB Output is correct
24 Correct 562 ms 243608 KB Output is correct