Submission #753501

#	Time	Username	Problem	Language	Result	Execution time	Memory
753501		MetalPower	Park (BOI16_park)	C++14	0 / 100	245 ms	28312 KiB

park

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define pli pair<int, pii>
#define fi first
#define se second

const int MX = 2e3 + 10;
const int MN = 1e5 + 10;

int N, M, W, H, x[MX], y[MX], r[MX];
vector<pli> edges; // weight, u, v
vector<pli> queries;

string ans[MN];

struct dsu{
	int p[MX];

	void init(){
		for(int i = 0; i < MX; i++) p[i] = i;
	}

	int f(int x){
		if(p[x] == x) return x;
		else return p[x] = f(p[x]);
	}

	void Join(int u, int v){
		int fu = f(u), fv = f(v);
		if(fu == fv) return;
		p[fu] = fv;
	}
} D;

int diff(int a, int b){
	return a > b ? a - b : b - a;
}

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

	cin >> N >> M >> W >> H;

	D.init();

	for(int i = 1; i <= N; i++){
		cin >> x[i] >> y[i] >> r[i];
		edges.push_back({(x[i] - r[i]) / 2, {N + 1, i}}); // maximum radius that can pass, aka is disconnected
		edges.push_back({(y[i] - r[i]) / 2, {N + 2, i}}); 
		edges.push_back({(W - x[i] - r[i]) / 2, {N + 3, i}});
		edges.push_back({(H - y[i] - r[i]) / 2, {N + 4, i}});
	}

	for(int i = 1; i <= N; i++){
		for(int j = i + 1; j <= N; j++){
			int dx = diff(x[i], x[j]), dy = diff(y[i], y[j]);
			int dist = sqrt(1ll * dx * dx + 1ll * dy * dy) - r[i] - r[j];
			edges.push_back({dist / 2, {i, j}});
		}
	}

	for(int i = 1; i <= M; i++){
		int rd, st; cin >> rd >> st;
		queries.push_back({rd, {st, i}});
	}

	int sz = edges.size();
	sort(edges.begin(), edges.end());
	sort(queries.begin(), queries.end());

	int j = 0;
	for(pli q : queries){
		for(; edges[j].fi < q.fi && j < sz; j++) D.Join(edges[j].se.fi, edges[j].se.se);

		for(int i = 1; i <= 4; i++){
			if(q.se.fi == i) ans[q.se.se] += (char)(i + '0');
			else{
				bool st = D.f(N + q.se.fi) != D.f(N + q.se.fi % 4 + 1);
				bool fn = D.f(N + i) != D.f(N + i % 4 + 1);
				if(st && fn) ans[q.se.se] += (char)(i + '0');
			}
		}
	}

	for(int i = 1; i <= M; i++) cout << ans[i] << '\n';
}

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