제출 #932681

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
932681		Angus_Yeung	Park (BOI16_park)	C++14	27 / 100	202 ms	57280 KiB

park

#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<ll, ll>
typedef long long ll;
const ll MOD = 1000000007LL;
const ll INF = 1e15;
using namespace std;

struct tree {
	ll x, y, r;
};

struct visitor {
	ll e, r, id;
	string ans;
};

struct dista {
	ll id1, id2, dis;
	dista(ll id1, ll id2, ll dis): id1(id1), id2(id2), dis(dis) {}
};

ll n, m, w, h, p[2020];
tree a[2010];
visitor b[100010];
vector<dista> v;
bool tmp[10][10];

ll f(ll i, ll j) {
	return floor(sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)))-a[i].r-a[j].r;
}

ll find(ll x) {
	if (p[x] == x) return x;
	return p[x] = find(p[x]);
}

int main() {
	cin.tie(0); cout.tie(0);
	ios::sync_with_stdio(0);
	
	cin >> n >> m;
	cin >> w >> h;
	
	p[n+1] = n+1;
	p[n+2] = n+2;
	p[n+3] = n+3;
	p[n+4] = n+4;
	for (int i = 1; i <= n; i++) {
		p[i] = i;
		cin >> a[i].x >> a[i].y >> a[i].r;
		for (int j = 1; j < i; j++) {
			v.push_back(dista(j, i, f(i, j)));
		}
		v.push_back(dista(i, n+1, a[i].y-a[i].r));
		v.push_back(dista(i, n+2, w-a[i].x-a[i].r));
		v.push_back(dista(i, n+3, h-a[i].y-a[i].r));
		v.push_back(dista(i, n+4, a[i].x-a[i].r));
	}
	sort(v.begin(), v.end(), [&](dista x, dista y) -> bool {
		return x.dis > y.dis;
	});
	
	for (int i = 1; i <= m; i++) {
		cin >> b[i].r >> b[i].e;
		b[i].id = i;
	}
	sort(b+1, b+m+1, [&](visitor x, visitor y) -> bool {
		return x.r < y.r;
	});
	
	for (int i = 1; i <= m; i++) {
		while (!v.empty() && v.back().dis < 2*b[i].r) {
			p[find(v.back().id1)] = p[find(v.back().id2)];
			v.pop_back();
		}
		for (int j = 0; j < 15; j++) {
			tmp[j/4+1][j%4+1] = 1;
		}
		for (int j = 1; j <= 4; j++) {
			ll xx = j, yy = j%4+1;
			if (find(n+xx) != find(n+yy)) continue;
			for (int k = 1; k <= 4; k++) {
				if (k == yy) continue;
				tmp[k][yy] = tmp[yy][k] = 0;
			}
		}
		if (find(n+1) == find(n+3)) {
			tmp[1][2] = tmp[1][3] = tmp[2][1] = tmp[3][1] = 0;
			tmp[4][2] = tmp[4][3] = tmp[2][4] = tmp[3][4] = 0;
		}
		if (find(n+2) == find(n+4)) {
			tmp[1][4] = tmp[1][3] = tmp[4][1] = tmp[3][1] = 0;
			tmp[4][2] = tmp[2][3] = tmp[2][4] = tmp[3][2] = 0;
		}
		b[i].ans = "";
		for (int j = 1; j <= 4; j++) {
			if (tmp[b[i].e][j]) b[i].ans += '0'+j;
		}
	}
	sort(b+1, b+m+1, [&](visitor x, visitor y) -> bool {
		return x.id < y.id;
	});
	
	for (int i = 1; i <= m; i++) cout << b[i].ans << "\n";
	
	return 0;
}
/*

5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1

*/

• Subtask 1: 27 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42