Submission #1186943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186943		prism7k	Park (BOI16_park)	C++20	100 / 100	247 ms	35244 KiB

park

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

class DisjointSets {
	private:
		vector<int> parents;
		vector<int> sizes;
		
	public:
		DisjointSets(int sz) : parents(sz + 1), sizes(sz + 1, 1) {
			for(int i = 0; i <= sz; ++i) parents[i] = i;
		}
		
		int find(int x) {
			return parents[x] == x ? x : (parents[x] = find(parents[x]));
		}
		
		void unite(int x, int y) {
			int xr = find(x);
			int yr = find(y);
			if(xr == yr) return;
			
			if(sizes[xr] < sizes[yr]) swap(xr, yr);
			parents[yr] = xr;
			sizes[xr] += sizes[yr];
		}
		
		bool same(int x, int y) {
			return find(x) == find(y);
		}
};

struct tree {
	int x, y, r, id;
};

struct edge {
	int u, v;
	double w;
	
	bool operator<(const edge &other) {
		return w < other.w;
	}
};

struct visitor {
	int r, e, id;
	
	bool operator<(const visitor &other) {
		return r < other.r;
	}
};

bool l[100005][4];

vector<tree> trees;
vector<edge> edges;
vector<visitor> visitors;

int main() {
	memset(l, 0, sizeof l);
	int n, m; cin >> n >> m;
	int w, h; cin >> w >> h;
	
	auto get_dist = [&](int x1, int x2, int y1, int y2, int r1, int r2) {
		return sqrt(1LL * (x1 - x2) * (x1 - x2) + 1LL * (y1 - y2) * (y1 - y2)) - r1 - r2;
	};
	
	for(int i = 0; i < n; ++i) {
		int x, y, r;
		cin >> x >> y >> r;
		trees.push_back({x, y, r, i + 4});
		edges.push_back({0, i + 4, get_dist(0, x, y, y, 0, r)});
		edges.push_back({1, i + 4, get_dist(x, x, 0, y, 0, r)});
		edges.push_back({2, i + 4, get_dist(x, w, y, y, 0, r)});
		edges.push_back({3, i + 4, get_dist(x, x, y, h, 0, r)});
	}
	
	for(int i = 0; i < n - 1; ++i) {
		tree a = trees[i];
		for(int j = i + 1; j < n; ++j) {
			tree b = trees[j];
			edges.push_back({a.id, b.id, get_dist(a.x, b.x, a.y, b.y, a.r, b.r)});
		}
	}
	
	for(int i = 0; i < m; ++i) {
		int r, e;
		cin >> r >> e;
		visitors.push_back({r, --e, i});
	}
	
	int edge_id = 0;
	sort(edges.begin(), edges.end());
	sort(visitors.begin(), visitors.end());
	DisjointSets dsu(n + 4);
	
	for(auto[vis_r, vis_e, vis_id] : visitors) {
		while(edge_id < (int)edges.size() && edges[edge_id].w < 2 * vis_r) {
			edge cur = edges[edge_id];
			dsu.unite(cur.u, cur.v);
			edge_id++;
		}
		
		bool ltr = dsu.same(0, 2), btt = dsu.same(1, 3);
		bool ltb = dsu.same(0, 1), btr = dsu.same(1, 2);
		bool rtt = dsu.same(2, 3), ttl = dsu.same(3, 0);
		
		// bottom left
		if(
			vis_e == 0 ||
			(vis_e == 1 && !btr && !ltb && !btt) ||
			(vis_e == 2 && !rtt && !ltb && !btt && !ltr) ||
			(vis_e == 3 && !ttl && !ltb && !ltr)
		) l[vis_id][0] = true;
		// bottom right
		if(
			vis_e == 1 ||
			(vis_e == 0 && !ltb && !btr && !btt) ||
			(vis_e == 2 && !rtt && !btr && !ltr) ||
			(vis_e == 3 && !ttl && !btr && !btt && !ltr)
		) l[vis_id][1] = true;
		// top right
		if(
			vis_e == 2 ||
			(vis_e == 0 && !ltb && !rtt && !btt && !ltr) ||
			(vis_e == 1 && !btr && !rtt && !ltr) ||
			(vis_e == 3 && !ttl && !rtt && !btt)
		) l[vis_id][2] = true;
		// top left
		if(
			vis_e == 3 ||
			(vis_e == 0 && !ltb && !ttl && !ltr) ||
			(vis_e == 1 && !btr && !ttl && !ltr && !btt) ||
			(vis_e == 2 && !rtt && !ttl && !btt)
		) l[vis_id][3] = true;
	}
	
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < 4; ++j) {
			if (l[i][j]) cout << j + 1;
		}
		cout << "\n";
	}
}

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