Submission #378029

#	Time	Username	Problem	Language	Result	Execution time	Memory
378029		MahdiBahramian	Park (BOI16_park)	C++17	0 / 100	9 ms	7784 KiB

park

#include<bits/stdc++.h>
#define F first
#define S second
#define make make_pair
#define pb push_back
using namespace std;
const int Max = 1e3 + 10;

int X[Max] , Y[Max] , R[Max];
int S[Max]; pair<int , int> Q[Max];
vector<pair<int , pair<int , int>>> E;
string ans[100010];

int par[Max];
int PAR(int a)
{
	if(par[a] == a) return a;
	return par[a] = PAR(par[a]);
}
void UNI(int a , int b)
{
	//cout << "uni " << a << ' ' << b << '\n';
	a = PAR(a);
	b = PAR(b);
	if(a != b) par[a] = b;
}

int main()
{
	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
	int n , m , w , h; cin >> n >> m >> w >> h;
	for(int i = 1 ; i <= n + 4 ; i++) par[i] = i;

	for(int i = 1 ; i <= n ; i++)
		cin >> X[i] >> Y[i] >> R[i];
	
	for(int i = 1 ; i <= n ; i++)
	{
		for(int j = i + 1 ; j <= n ; j++)
		{
			double dx = X[i] - X[j];
			double dy = Y[i] - Y[j];
			double dst = sqrt(dx * dx + dy * dy) - R[i] - R[j];
			//int w = dst + 1;
			int w = 0;
			E.pb(make(w , make(i , j)));
		}
		int wl = X[i] - R[i] + 1;
		int wr = w - X[i] - R[i] + 1;
		int wu = Y[i] - R[i] + 1;
		int wd = h - Y[i] - R[i] + 1;
		E.pb(make(wl , make(i , n + 1)));
		E.pb(make(wu , make(i , n + 2)));
		E.pb(make(wr , make(i , n + 3)));
		E.pb(make(wd , make(i , n + 4)));
	}
	for(int i = 1 ; i <= m ; i++)
	{
		int r; cin >> r >> S[i];
		r *= 2;
		Q[i] = make(r , i);
	}
	sort(Q + 1 , Q + m + 1);
	sort(E.begin() , E.end());
	int j = 1;
	for(int i = 0 ; i < E.size() ; i++)
	{
		while(j <= m && Q[j].F < E[i].F)
		{
			int i = Q[j].S;
			int l = PAR(n + 1);
			int u = PAR(n + 2);
			int r = PAR(n + 3);
			int d = PAR(n + 4);
			int s = S[i];
			//cout << "ans " << i << "   " << s << " , " << l << ',' << r << ',' << u << ',' << d << '\n'; 
			if(s == 1)
			{
				if(l != d && l != r && l != u) ans[i] += '4';
				if(d != l && d != u && d != r) ans[i] += '2';
				if(l != r && u != d && u != r && d != l) ans[i] += '3';
				ans[i] += '1';
			}
			else if(s == 2)
			{
				if(d != l && d != r && d != u) ans[i] += '1';
				if(r != l && r != d && r != u) ans[i] += '3';
				if(r != d && u != l && u != d && l != r) ans[i] += '4';
				ans[i] += '2';
			}
			else if(s == 3)
			{
				if(u != l && u != r && u != d) ans[i] += '4';
				if(r != l && r != u && r != d) ans[i] += '2';
				if(l != r && u != d && u != r && d != l) ans[i] += '1';
				ans[i] += '3';
			}
			else
			{
				if(u != l && u != r && u != d) ans[i] += '3';
				if(l != r && l != u && l != d) ans[i] += '1';
				if(r != d && u != l && u != d && l != r) ans[i] += '2';
				ans[i] += '4';
			}
			j++;
		}
		//cout << E[i].F << ' ';
		UNI(E[i].S.F , E[i].S.S);
	}
	while(j <= m)
	{
		int i = Q[j].S;
		int l = PAR(n + 1);
		int u = PAR(n + 2);
		int r = PAR(n + 3);
		int d = PAR(n + 4);
		int s = S[i];
		//cout << "ans " << i << "   " << s << " , " << l << ',' << r << ',' << u << ',' << d << '\n'; 
		if(s == 1)
		{
			if(l != d && l != r && l != u) ans[i] += '4';
			if(d != l && d != u && d != r) ans[i] += '2';
			if(l != r && u != d && u != r && d != l) ans[i] += '3';
			ans[i] += '1';
		}
		else if(s == 2)
		{
			if(d != l && d != r && d != u) ans[i] += '1';
			if(r != l && r != d && r != u) ans[i] += '3';
			if(r != d && u != l && u != d && l != r) ans[i] += '4';
			ans[i] += '2';
		}
		else if(s == 3)
		{
			if(u != l && u != r && u != d) ans[i] += '4';
			if(r != l && r != u && r != d) ans[i] += '2';
			if(l != r && u != d && u != r && d != l) ans[i] += '1';
			ans[i] += '3';
		}
		else
		{
			if(u != l && u != r && u != d) ans[i] += '3';
			if(l != r && l != u && l != d) ans[i] += '1';
			if(r != d && u != l && u != d && l != r) ans[i] += '2';
			ans[i] += '4';
		}
		j++;
	}
	
	for(int i = 1 ; i <= m ; i++) sort(ans[i].begin() , ans[i].end()) , cout << ans[i] << '\n';
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:43:11: warning: unused variable 'dst' [-Wunused-variable]
   43 |    double dst = sqrt(dx * dx + dy * dy) - R[i] - R[j];
      |           ^~~
park.cpp:66:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  for(int i = 0 ; i < E.size() ; i++)
      |                  ~~^~~~~~~~~~

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