Submission #257427

#	Time	Username	Problem	Language	Result	Execution time	Memory
257427		vioalbert	Park (BOI16_park)	C++14	100 / 100	428 ms	50092 KiB

park

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const int N = 2e3+20;
int n, m;
ll w, h;
ll x[N], y[N], r[N];
struct edge {
	ll u, v, w;
	bool operator<(const edge& ot) {
		return w < ot.w;
	}
};
ll c[5][5], ans[5][5];
vector<edge> edges;

void read() {
	cin >> n >> m >> w >> h;
	for(int i = 1; i <= n; i++)
		cin >> x[i] >> y[i] >> r[i];
}

ll costToCircle(int i, int j) {
	ll xx = (x[i] - x[j]), yy = (y[i] - y[j]);
	return (ll)sqrt(xx * xx + yy * yy) - r[i] - r[j];
}

ll costToWall(int i, int j) {
	if(j == 1) {	//down
		return y[i] - r[i];
	} else if(j == 2) {	//right
		return w - x[i] - r[i];
	} else if(j == 3) {	//up
		return h - y[i] - r[i];
	} else if(j == 4) {	//left
		return x[i] - r[i];
	}
}

int par[N];

int find(int u) {
	if(u == par[u]) return u;
	else return par[u] = find(par[u]);
}

void join(int u, int v) {
	int parU = find(u), parV = find(v);
	par[parU] = parV;
}

void solve() {
	for(int i = 1; i <= n; i++) {
		for(int j = i+1; j <= n; j++) {
			ll cost = costToCircle(i, j);
			edges.push_back({i, j, cost});
		}
		for(int j = 1; j <= 4; j++) {
			ll cost = costToWall(i, j);
			edges.push_back({i, j+n, cost});
		}
	}
	sort(edges.begin(), edges.end());

	for(int i = 1; i <= n+4; i++)
		par[i] = i;
	for(int i = 1; i <= 4; i++) {
		for(int j = i+1; j <= 4; j++)
			c[i][j] = -1;
	}

	for(edge e : edges) {
		if(find(e.u) != find(e.v)) {
			join(e.u, e.v);
		}
		for(int i = 1; i <= 4; i++) {
			for(int j = i+1; j <= 4; j++) {
				if(find(i+n) == find(j+n) && c[i][j] == -1)
					c[i][j] = e.w;
			}
		}
	}

	ans[1][2] = ans[2][1] = min({c[1][4], c[1][3], c[1][2]});
	ans[1][3] = ans[3][1] = min({c[1][4], c[1][3], c[2][4], c[2][3]});
	ans[1][4] = ans[4][1] = min({c[1][4], c[2][4], c[3][4]});
	ans[2][3] = ans[3][2] = min({c[1][2], c[2][4], c[2][3]});
	ans[2][4] = ans[4][2] = min({c[1][2], c[1][3], c[2][4], c[3][4]});
	ans[3][4] = ans[4][3] = min({c[2][3], c[1][3], c[3][4]});

	while(m--) {
		ll k; int e; cin >> k >> e;
		for(int i = 1; i <= 4; i++) {
			if(e == i || k * 2 <= ans[e][i])
				cout << i;
		}
		cout << '\n';
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	read();
	solve();
	return 0;
}

Compilation message (stderr)

park.cpp: In function 'll costToWall(int, int)':
park.cpp:40:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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