Submission #1066832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066832		kunzaZa183	Park (BOI16_park)	C++17	100 / 100	256 ms	54420 KiB

park

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

int par(int cur, vector<int>& ds) {
	if (ds[cur] == cur)
		return cur;
	ds[cur] = par(ds[cur], ds);
	return ds[cur];
};

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m;
	cin >> n >> m;
	int w, h;
	cin >> w >> h;

	struct tree {
		int x, y, r;
	};
	vector<tree> vt(n);
	for (auto& a : vt)
		cin >> a.x >> a.y >> a.r;

	struct edge {
		int a, b, w;
		edge() {}
		edge(int x, int y, int z) {
			a = x, b = y, w = z;
		}
	};

	auto dis = [](tree a, tree b) {
		return int64_t(sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)) + 1e-5) - a.r - b.r;
	};

	vector<edge> ve;
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++) {
			ve.emplace_back(i, j, dis(vt[i], vt[j]));
		}

	for (int i = 0; i < n; i++) {
		ve.emplace_back(i, n, vt[i].y - vt[i].r);
		ve.emplace_back(i, n + 1, w - vt[i].x - vt[i].r);
		ve.emplace_back(i, n + 2, vt[i].x - vt[i].r);
		ve.emplace_back(i, n + 3, h - vt[i].y - vt[i].r);
	}

	sort(ve.begin(), ve.end(), [&](edge a, edge b) {
		return a.w < b.w;
		});

	int alive[4][4];

	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			alive[i][j] = 1;

	auto kill = [&](vector<int> vi, vector<int> vi2) {

		for (auto a : vi)
			for (auto b : vi2)
				alive[a][b] = 0;

		for (auto a : vi2)
			for (auto b : vi)
				alive[a][b] = 0;
	};

	struct qry {
		int r, start;
		int in;
	};
	vector<qry> vq(m);
	for (int i = 0; i < m; i++) {
		cin >> vq[i].r >> vq[i].start;
		vq[i].in = i;
		vq[i].start--;
	}
	sort(vq.begin(), vq.end(), [](qry a, qry b) {
		return a.r < b.r;
		});

	vector<int> dsu(n + 4);
	iota(dsu.begin(), dsu.end(), 0);


	vector<string> ans(m);

	int in = 0, in2 = 0;
	while (in < ve.size() && in2 < m) {
		if (vq[in2].r * 2 <= ve[in].w) {
			vector<int> ds2(4);
			iota(ds2.begin(), ds2.end(), 0);

			for (int i = 0; i < 4; i++)
				for (int j = 0; j < 4; j++)
					if (alive[i][j])
						ds2[par(i, ds2)] = par(j, ds2);

			for (int i = 0; i < 4; i++)
				if (par(i, ds2) == par(vq[in2].start, ds2)) {
					ans[vq[in2].in].push_back('1' + i);
				}

			in2++;
		}
		else {
			dsu[par(ve[in].a, dsu)] = par(ve[in].b, dsu);

			if (par(n, dsu) == par(n + 3, dsu))
				kill({ 0, 3 }, { 1, 2 });
			if (par(n + 1, dsu) == par(n + 2, dsu))
				kill({ 0,1 }, { 2,3 });
			if (par(n, dsu) == par(n + 1, dsu))
				kill({ 1 }, { 0,2,3 });
			if (par(n, dsu) == par(n + 2, dsu))
				kill({ 0 }, { 1,2,3 });
			if (par(n + 2, dsu) == par(n + 3, dsu))
				kill({ 3 }, { 0,1,2 });
			if (par(n + 1, dsu) == par(n + 3, dsu))
				kill({ 2 }, { 0,1,3 });
			in++;
		}
	}

	while (in2 < m) {
		vector<int> ds2(4);
		iota(ds2.begin(), ds2.end(), 0);

		for (int i = 0; i < 4; i++)
			for (int j = 0; j < 4; j++)
				if (alive[i][j])
					ds2[par(i, ds2)] = par(j, ds2);

		for (int i = 0; i < 4; i++)
			if (par(i, ds2) == par(vq[in2].start, ds2)) {
				ans[vq[in2].in].push_back('1' + i);
			}

		in2++;
	}

	for (auto a : ans)
		cout << a << "\n";

}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:93:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<main()::edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  while (in < ve.size() && in2 < m) {
      |         ~~~^~~~~~~~~~~

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