oj.uz

Submission #350887

# Submission time Handle Problem Language Result Execution time Memory
350887 2021-01-19T09:37:03 Z saniyar_krmi Park (BOI16_park) C++14
31 / 100
 298 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];
ll 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
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 298 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 220144 KB Output is correct
2 Correct 254 ms 219876 KB Output is correct
3 Correct 235 ms 219876 KB Output is correct
4 Correct 248 ms 219880 KB Output is correct
5 Correct 248 ms 219996 KB Output is correct
6 Correct 225 ms 219996 KB Output is correct
7 Correct 220 ms 220004 KB Output is correct
8 Correct 224 ms 219976 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 298 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -