Submission #989906

#	Time	Username	Problem	Language	Result	Execution time	Memory
989906		michified	Park (BOI16_park)	C++17	100 / 100	305 ms	30584 KiB

park

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

class UnionFind {
public:
	vector<int> root, rank;
	UnionFind(int n) {
		root.resize(n);
		rank.resize(n);
		for (int i = 0; i < n; i++) {
			root[i] = i;
			rank[i] = 1;
		}
	}

	int find(int a) {
		if (a == root[a]) return a;
		return root[a] = find(root[a]);
	}

	void join(int a, int b) {
		int roota = find(a), rootb = find(b);
		if (roota != rootb) {
			if (rank[roota] < rank[rootb]) root[rootb] = roota;
			else if (rank[rootb] < rank[roota]) root[roota] = rootb;
			else {
				root[roota] = rootb;
				rank[rootb]++;
			}
		}
	}

	bool cnctd(int a, int b) {
		return find(a) == find(b);
	}
};

struct tree_t {
	int x, y, r;
};

struct person_t {
	int r, e, ind;
};

struct edge_t {
	int one, two, dist;
};

int dist(tree_t& a, tree_t& b) {
	return (int) floor(sqrt((ll) abs(a.x - b.x) * abs(a.x - b.x) + (ll) abs(a.y - b.y) * abs(a.y - b.y))) - a.r - b.r;
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int w, h, n, m, i, j;
	cin >> n >> m >> w >> h;
	vector<tree_t> trees(n);
	for (i = 0; i < n; i++) cin >> trees[i].x >> trees[i].y >> trees[i].r;
	vector<person_t> ppl(m);
	for (i = 0; i < m; i++) {
		cin >> ppl[i].r >> ppl[i].e;
		ppl[i].ind = i;
	}
	sort(ppl.begin(), ppl.end(), [](const person_t& a, const person_t& b){return a.r < b.r;});
	vector<edge_t> edges; // n: top, n + 1: bottom, n + 2: left, n + 3: right
	for (i = 0; i < n; i++) {
		for (j = i + 1; j < n; j++) {
			edges.push_back({i, j, dist(trees[i], trees[j])});
		} 
	}
	for (i = 0; i < n; i++) { 
		tree_t tmp = {trees[i].x, h, 0};
		edges.push_back({i, n, dist(trees[i], tmp)});
		tmp = {trees[i].x, 0, 0};
		edges.push_back({i, n + 1, dist(trees[i], tmp)});	
		tmp = {0, trees[i].y, 0};
		edges.push_back({i, n + 2, dist(trees[i], tmp)});	
		tmp = {w, trees[i].y, 0};
		edges.push_back({i, n + 3, dist(trees[i], tmp)});	
	}
	UnionFind uf(n + 4);
	sort(edges.begin(), edges.end(), [](const edge_t& a, const edge_t& b){return a.dist < b.dist;});
	int cur = 0;
	vector<string> ans(m);
	for (person_t& p : ppl) {
		while (edges[cur].dist < p.r * 2) {
			uf.join(edges[cur].one, edges[cur].two);
			cur++;
		}
		bool tl, tr, bl, br;
		bool ud = uf.cnctd(n, n + 1), lr = uf.cnctd(n + 2, n + 3), ul = uf.cnctd(n, n + 2), ur = uf.cnctd(n, n + 3), dl = uf.cnctd(n + 1, n + 2), dr = uf.cnctd(n + 1, n + 3);

		// 1: bottom left
		tl = p.e == 4 and not (lr or ul or dl);
		tr = p.e == 3 and not (ud or lr or ur or dl);
		bl = p.e == 1;
		br = p.e == 2 and not (ud or dr or dl);
		if (tl or tr or bl or br) ans[p.ind] += '1';

		// 2: bottom right
		tl = p.e == 4 and not (ud or lr or ul or dr);
		tr = p.e == 3 and not (lr or ur or dr);
		bl = p.e == 1 and not (ud or dr or dl);
		br = p.e == 2;
		if (tl or tr or bl or br) ans[p.ind] += '2';

		// 3: top right
		tl = p.e == 4 and not (ud or ul or ur);
		tr = p.e == 3;
		bl = p.e == 1 and not (ud or lr or ur or dl);
		br = p.e == 2 and not (lr or ur or dr);
		if (tl or tr or bl or br) ans[p.ind] += '3';

		// 4: top left
		tl = p.e == 4;
		tr = p.e == 3 and not (ud or ul or ur);
		bl = p.e == 1 and not (lr or ul or dl);
		br = p.e == 2 and not (ud or lr or ul or dr);
		if (tl or tr or bl or br) ans[p.ind] += '4';
	}
	for (i = 0; i < m; i++) cout << ans[i] << endl;
	return 0;
}

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