제출 #634166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
634166		SharpEdged	Park (BOI16_park)	C++17	100 / 100	311 ms	55904 KiB

park

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define pb push_back
#define eb emplace_back
#define sz(x) ((int)x.size())

typedef long long ll;

using namespace std;

// the below program uses squares of distances for that neat no-"double" usage code

vector<int> par, rnk;
vector<vector<int>> con;
vector<ll> x, y, r;

vector<vector<int>> adj(4, vector<int>(4));

void updateAdj(int a){
	for (int i = 0; i < 4; i++){
		if (!con[a][i]) continue;
		for (int j = 0; j < 4; j++){
			if (!con[a][j]) continue;
			adj[i][j] = 1;
		}
	}
}

int findP(int a){
	return par[a] = (par[a] == a) ? a : findP(par[a]);
}

void unite(int a, int b){
	a = findP(a); b = findP(b);
	if (a == b) return;
	if (rnk[a] > rnk[b]) swap(a, b);
	if (rnk[a] == rnk[b]) rnk[b]++;
	par[a] = b;
	for (int i = 0; i < 4; i++){ con[b][i] |= con[a][i]; }
	updateAdj(b);
}

void connect(int a, int wall){
	a = findP(a);
	con[a][wall] = 1;
	updateAdj(a);
}

struct Link {
	int a, b, wall;
	ll dist;
	Link(int _a, int _b, ll _dist, int _wall) {
		a = _a; b = _b; dist = _dist; wall = _wall;
	}
	bool operator<(const Link& other) const {
		return dist < other.dist;
	}
	bool Join(double len){
		if (len <= dist) return 0;
		
		if (wall) connect(a, b);
		else unite(a, b);
		return 1;
	}
};

struct Query{
	ll r; int e, id;
	Query(ll _r, int _e, int _id) {
		r = _r; e = _e; id = _id;
	}
	bool operator<(const Query& other) const {
		return r < other.r;
	}
};

void printAdj(){
	cout << "??\n\n";
	for (int i = 0; i < 4; i++){
		for (int j = 0; j < 4; j++){
			cout << adj[i][j] << " ";
		}
		cout << "\n";
	}
}

string GetAns(int e){
	int prev = (e + 3) % 4;
	int mid = (e + 2) % 4;
	int nxt = (e + 1) % 4;
	vector<int> ok = { e+1 };
	
	//printAdj();
	
	// e -> next
	if (!adj[nxt][e] && !adj[nxt][mid] && !adj[nxt][prev]) ok.pb(nxt+1);
	// e -> middle
	if (!adj[e][nxt] && !adj[mid][prev] && !adj[e][mid] && !adj[nxt][prev]) ok.pb(mid+1);
	// e -> previous
	if (!adj[e][prev] && !adj[e][mid] && !adj[e][nxt]) ok.pb(prev+1);
	
	string res = "";
	sort(all(ok));
	for (int i = 0; i < sz(ok); i++) res += to_string(ok[i]);
	return res;
}

char nl = '\n';

int main() {
	int n, m;
	ll w, h;
	cin >> n >> m >> w >> h;
	x.resize(n); y.resize(n); r.resize(n);
	vector<Link> links;
	for (int i = 0; i < n; i++){
		par.pb(i); rnk.pb(0); con.pb(vector<int>(4));
		cin >> x[i] >> y[i] >> r[i];
		links.eb(i, 0, x[i] - r[i], 1);
		links.eb(i, 1, y[i] - r[i], 1);
		links.eb(i, 2, w - x[i] - r[i], 1);
		links.eb(i, 3, h - y[i] - r[i], 1);
	}
	for (int i = 0; i < n; i++){
		for (int j = i+1; j < n; j++){
			ll dx = x[i] - x[j];
			ll dy = y[i] - y[j];
			links.eb(i, j, sqrt(dx * dx + dy * dy) - r[i] - r[j], 0);
		}
	}
	vector<string> ans(m);
	vector<Query> qrys;
	for (int i = 0; i < m; i++){
		ll rad; int e;
		cin >> rad >> e;
		qrys.eb(rad, e-1, i);
	}

	sort(all(qrys));
	sort(all(links));

	int curLink = 0;

	for (int i = 0; i < m; i++) {
		ll rad = qrys[i].r; int e = qrys[i].e, id = qrys[i].id;

		while (curLink < sz(links) && links[curLink].Join(2*rad)) {
			curLink++;
		}
		
		ans[id] = GetAns(e);
	}

	for (int i = 0; i < m; i++) cout << ans[i] << nl;
	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: 31 / 31
• Subtask 3: 42 / 42