Submission #350888

#	Time	Username	Problem	Language	Result	Execution time	Memory
350888		saniyar_krmi	Park (BOI16_park)	C++14	58 / 100	902 ms	262148 KiB

park

// 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 / 27
• Subtask 2: 31 / 31
• Subtask 3: 0 / 42