oj.uz

Submission #350866

# Submission time Handle Problem Language Result Execution time Memory
350866 2021-01-19T09:26:30 Z saniyar_krmi Park (BOI16_park) C++14
58 / 100
 907 ms 262148 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<ld, pii>> all;
ld tx[maxn], ty[maxn], tr[maxn];

int p[maxn], sz[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;
	if(sz[a] < sz[b])
		swap(a, b);
	p[b] = a, sz[a] += sz[b];
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);  cout.tie(0);

	for(int i=0; i<maxn; i++) p[i] = i, sz[i] = 1;

	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++){
			ld 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}});
	}

	ld 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 884 ms 262048 KB Output is correct
2 Correct 893 ms 262144 KB Output is correct
3 Correct 891 ms 262144 KB Output is correct
4 Correct 888 ms 262052 KB Output is correct
5 Correct 907 ms 262040 KB Output is correct
6 Correct 884 ms 262040 KB Output is correct
7 Correct 751 ms 262140 KB Output is correct
8 Correct 755 ms 262060 KB Output is correct
9 Correct 137 ms 196116 KB Output is correct
10 Correct 131 ms 196076 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 201364 KB Output is correct
2 Correct 229 ms 201584 KB Output is correct
3 Correct 220 ms 201520 KB Output is correct
4 Correct 221 ms 201436 KB Output is correct
5 Correct 215 ms 201436 KB Output is correct
6 Correct 217 ms 201436 KB Output is correct
7 Correct 231 ms 201316 KB Output is correct
8 Correct 213 ms 201444 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 884 ms 262048 KB Output is correct
2 Correct 893 ms 262144 KB Output is correct
3 Correct 891 ms 262144 KB Output is correct
4 Correct 888 ms 262052 KB Output is correct
5 Correct 907 ms 262040 KB Output is correct
6 Correct 884 ms 262040 KB Output is correct
7 Correct 751 ms 262140 KB Output is correct
8 Correct 755 ms 262060 KB Output is correct
9 Correct 137 ms 196116 KB Output is correct
10 Correct 131 ms 196076 KB Output is correct
11 Correct 218 ms 201364 KB Output is correct
12 Correct 229 ms 201584 KB Output is correct
13 Correct 220 ms 201520 KB Output is correct
14 Correct 221 ms 201436 KB Output is correct
15 Correct 215 ms 201436 KB Output is correct
16 Correct 217 ms 201436 KB Output is correct
17 Correct 231 ms 201316 KB Output is correct
18 Correct 213 ms 201444 KB Output is correct
19 Runtime error 462 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -