Submission #113353

#	Time	Username	Problem	Language	Result	Execution time	Memory
113353		Mahdi_Jfri	Park (BOI16_park)	C++14	100 / 100	732 ms	117380 KiB

park

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

#define ll long long
#define pb push_back
#define ld long double

const int maxn = 2e3 + 20;
const int maxm = maxn * maxn / 2 + 20;
const int maxq = 1e5 + 20;

int x[maxn] , y[maxn] , r[maxn] , e[maxq] , par[maxn] , n;

vector<int> query[maxm];

string res[maxq];

int root(int v)
{
	return (par[v] < 0? v : par[v] = root(par[v]));
}

bool cn(int a , int b)
{
	a %= 4 , b %= 4;
	a += n , b += n;

	a = root(a) , b = root(b);
	return (a == b);
}

void merge(int a , int b)
{
	a = root(a) , b = root(b);
	if(a != b)
		par[b] = a;
}

ld d(int i , int j)
{
	return sqrt(1LL * (x[i] - x[j]) * (x[i] - x[j]) + 1LL * (y[i] - y[j]) * (y[i] - y[j]));
}

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

	memset(par , -1 , sizeof par);

	int m , w , h;
	cin >> n >> m >> w >> h;

	for(int i = 0; i < n; i++)
		cin >> x[i] >> y[i] >> r[i];

	vector<pair<ld , pair<int , int> > > edge;
	for(int i = 0; i < n; i++)
	{
		for(int j = i + 1; j < n; j++)
		{
			ld w = (d(i , j) - r[i] - r[j]) / 2.0;
			edge.pb({w , {i , j}});
		}

		{
			ld w = (y[i] - r[i]) / 2.0;
			edge.pb({w , {i , n}});
		}

		{
			ld w = (x[i] - r[i]) / 2.0;
			edge.pb({w , {i , n + 3}});
		}

		{
			ld w = (h - y[i] - r[i]) / 2.0;
			edge.pb({w , {i , n + 2}});
		}

		{
			ld w1 = (w - x[i] - r[i]) / 2.0;
			edge.pb({w1 , {i , n + 1}});
		}
	}

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

	for(int i = 0; i < m; i++)
	{
		int r;
		cin >> r >> e[i];
		e[i]--;

		pair<ld , pair<int , int> > tmp = {r , {-1 , maxn}};
		int k = lower_bound(edge.begin() , edge.end() , tmp) - edge.begin();
		query[k].pb(i);
	}

	for(int i = 0; i <= (int)edge.size(); i++)
	{
		for(auto ind : query[i])
		{
			res[ind] = e[ind] + '1';
			int val = e[ind];
			// 1
			if(!cn(val , val + 1) && !cn(val , val + 2) && !cn(val , val + 3))
				res[ind] += (e[ind] + 1) % 4 + '1';

			// 2
			if(!cn(val , val + 3) && !cn(val , val + 2) && !cn(val + 1 , val + 2) && !cn(val + 1 , val + 3))
				res[ind] += (e[ind] + 2) % 4 + '1';

			// 3
			if(!cn(val + 3 , val) && !cn(val + 3 , val + 1) && !cn(val + 3 , val + 2))
				res[ind] += (e[ind] + 3) % 4 + '1';
		}

		if(i < (int)edge.size())
			merge(edge[i].second.first , edge[i].second.second);
	}

	for(int i = 0; i < m; i++)
	{
		sort(res[i].begin() , res[i].end());
		cout << res[i] << endl;
	}
}

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