Submission #389866

#	Time	Username	Problem	Language	Result	Execution time	Memory
389866		saleh	Park (BOI16_park)	C++17	0 / 100	637 ms	35960 KiB

park

#include <bits/stdc++.h>

#define ft first
#define sd second

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 2000 + 123, MAXM = 100 * 1000 + 123;














int n, m, w, h, x[MAXN], y[MAXN], r[MAXN], a[MAXM], R[MAXM], e[MAXM], g[MAXN][MAXN], par[MAXN];
deque<pii> v;
vector<int> ans[MAXM];
bitset<3 + 1 + 3 + 3> mark[1 + 3 + 3 + 3];

int dis(int z, int w) { return sqrt(1. * abs(x[z] - x[w]) * abs(x[z] - x[w]) + 1. * abs(y[z] - y[w]) * abs(y[z] - y[w])); }

int gp(int z) { return ~par[z]? par[z] = gp(par[z]): z; }
void mrg(int z, int w) {
	z = gp(z);
	w = gp(w);
	if (z != w) par[z] = w;
}
void cut(int z) { mark[z][1] = mark[z][3] = mark[z][4] = mark[z][2] = mark[1][z] = mark[3][z] = mark[4][z] = mark[2][z] = true; mark[z][z] = false; }


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	memset(par, -1, sizeof par);
	cin >> n >> m >> w >> h;
	for (int i = 0; i < n; i++) cin >> x[i] >> y[i] >> r[i];
	for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) {
		g[i][j] = g[j][i] = dis(i, j) - r[i] - r[j];
		v.push_back({i, j});
	}
	for (int i = 0; i < n; i++) {
		v.push_back({n, i});
		v.push_back({n + 1, i});
		v.push_back({n + 2, i});
		v.push_back({n + 3, i});
		g[n][i] = g[i][n] = y[i] - r[i];
		g[n + 1][i] = g[i][n + 1] = w - x[i] - r[i];
		g[n + 2][i] = g[i][n + 2] = h - y[i] - r[i];
		g[n + 3][i] = g[i][n + 3] = x[i] - r[i];
	}
	sort(v.begin(), v.end(), [](pii z, pii w) { return g[z.ft][z.sd] < g[w.ft][w.sd]; });
	for (int i = 0; i < m; i++) cin >> R[i] >> e[i];
	iota(a, a + m, 0);
	sort(a, a + m, [](int z, int w) { return R[z] < R[w]; });
	for (int i = 0; i < m; i++) {
		int j = a[i];
		while (!v.empty() && g[v.front().ft][v.front().sd] < (R[j] << 1)) {
			mrg(v.front().ft, v.front().sd);
			v.pop_front();
		}
		if (gp(n) == gp(n + 1)) cut(2);
		if (gp(n + 1) == gp(n + 2)) cut(3);
		if (gp(n + 2) == gp(n + 3)) cut(4);
		if (gp(n + 3) == gp(n)) cut(1);
		if (gp(n) == gp(n + 2)) mark[1][2] = mark[1][3] = mark[4][2] = mark[4][3] = mark[2][1] = mark[3][1] = mark[2][4] = mark[3][4] = true;
		if (gp(n + 1) == gp(n + 3)) mark[1][4] = mark[1][3] = mark[2][4] = mark[2][3] = mark[4][1] = mark[3][1] = mark[4][2] = mark[3][2] = true;
		for (int k = 1; k <= 4; k++) if (!mark[e[j]][k]) ans[j].push_back(k);
	}
	for (int i = 0; i < m; i++) {
		for (auto j : ans[i]) cout << j;
		cout << '\n';
	}
	return 0;
}

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