Submission #555894

#	Time	Username	Problem	Language	Result	Execution time	Memory
555894		Magi	Park (BOI16_park)	C++14	100 / 100	525 ms	66396 KiB

park

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define ll long long
#define ld long double
#define f first
#define s second

using namespace std;

const int NMAX = 2100, QMAX = 1e5;
const ld eps = 1e-9;
int n, m, w, h, tata[NMAX+10], rang[NMAX+10], viz[NMAX+10], sol[QMAX+10];
vector <pair <ld, pair <int, int> > > edge;
pair <int, pair <int, int> > q[QMAX+10];

struct circle{
	ll x, y, r;
	ld minRadiusEdge(int t){
		if(!t)
			return (y - r) * 0.5 + eps;
		if(t == 1)
			return (w - x - r) * 0.5 + eps;
		if(t == 2)
			return (h - y - r) * 0.5 + eps;
		return (x - r) * 0.5 + eps;
	}
	ld minRadiusCircle(circle other){
		ld dist = sqrt((ld)((x - other.x) * (x - other.x) + (y - other.y) * (y - other.y)));
		return (dist - r - other.r) * 0.5 + eps;
	}
}v[NMAX+10];

int findDaddy(int x){
	int r = x, y = x;
	while(r != tata[r])
		r = tata[r];
	while(x != tata[x]){
		y = tata[x];
		tata[x] = r;
		x = y;
	}
	return r;
}

void unite(int x, int y){
	if(rang[x] < rang[y])
		tata[x] = y;
	else
		tata[y] = x;
	if(rang[x] == rang[y])
		rang[x]++;
}

int main(){

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m >> w >> h;
	for(int i=1; i<=n; i++)
		cin >> v[i].x >> v[i].y >> v[i].r;

	for(int i=1; i<=n; i++){
		for(int t=0; t<4; t++){
			ld r = v[i].minRadiusEdge(t);
			edge.push_back({r, {i+3, t}});
		}
		for(int j=i+1; j<=n; j++){
			ld r = v[i].minRadiusCircle(v[j]);
			edge.push_back({r, {i+3, j+3}});
		}
	}

	sort(edge.begin(), edge.end());

	for(int i=1; i<=m; i++)
		cin >> q[i].f >> q[i].s.f, q[i].s.s = i;
	sort(q+1, q+m+1);

	for(int i=0; i<=n+3; i++)
		tata[i] = i, rang[i] = 1;

	int idx = 0;
	for(int i=1; i<=m; i++){
		while(idx < edge.size() && (ld)q[i].f > edge[idx].f){
			int val1 = findDaddy(edge[idx].s.f), val2 = findDaddy(edge[idx].s.s);
			idx++;
			if(val1 == val2)
				continue;
			unite(val1, val2);
		}
		for(int t=0; t<4; t++)
			viz[t] = findDaddy(t);

		int e = q[i].s.f - 1;
		bool ans[4];
		for(int t=0; t<4; t++)
			ans[t] = false;
		ans[e] = true;

		if(viz[e] != viz[(e+3)%4]){
			//adjacent counterclockwise
			if(viz[e] != viz[(e+2)%4] && viz[e] != viz[(e+1)%4])
				ans[(e+1)%4] = true;
			//opposite
			if(viz[e] != viz[(e+2)%4] && viz[(e+1)%4] != viz[(e+3)%4] && viz[(e+1)%4] != viz[(e+2)%4])
				ans[(e+2)%4] = true;
			//adjacent clockwise
			if(viz[(e+1)%4] != viz[(e+3)%4] && viz[(e+2)%4] != viz[(e+3)%4])
				ans[(e+3)%4] = true;
		}

		for(int t=0; t<4; t++)
			if(ans[t])
				sol[q[i].s.s] = sol[q[i].s.s] * 10 + (t + 1);
	}

	for(int i=1; i<=m; i++)
		cout << sol[i] << '\n';

	return 0;
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:87:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   while(idx < edge.size() && (ld)q[i].f > edge[idx].f){
      |         ~~~~^~~~~~~~~~~~~

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