oj.uz

Submission #113353

# Submission time Handle Problem Language Result Execution time Memory
113353 2019-05-25T06:53:34 Z Mahdi_Jfri Park (BOI16_park) C++14
100 / 100
 732 ms 117380 KB 
#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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 117148 KB Output is correct
2 Correct 560 ms 117232 KB Output is correct
3 Correct 600 ms 117292 KB Output is correct
4 Correct 558 ms 117148 KB Output is correct
5 Correct 537 ms 117148 KB Output is correct
6 Correct 536 ms 117276 KB Output is correct
7 Correct 507 ms 117380 KB Output is correct
8 Correct 508 ms 117320 KB Output is correct
9 Correct 42 ms 51320 KB Output is correct
10 Correct 41 ms 51320 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 53356 KB Output is correct
2 Correct 208 ms 53488 KB Output is correct
3 Correct 213 ms 53380 KB Output is correct
4 Correct 210 ms 53352 KB Output is correct
5 Correct 211 ms 53396 KB Output is correct
6 Correct 209 ms 53488 KB Output is correct
7 Correct 195 ms 52748 KB Output is correct
8 Correct 194 ms 52968 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 117148 KB Output is correct
2 Correct 560 ms 117232 KB Output is correct
3 Correct 600 ms 117292 KB Output is correct
4 Correct 558 ms 117148 KB Output is correct
5 Correct 537 ms 117148 KB Output is correct
6 Correct 536 ms 117276 KB Output is correct
7 Correct 507 ms 117380 KB Output is correct
8 Correct 508 ms 117320 KB Output is correct
9 Correct 42 ms 51320 KB Output is correct
10 Correct 41 ms 51320 KB Output is correct
11 Correct 208 ms 53356 KB Output is correct
12 Correct 208 ms 53488 KB Output is correct
13 Correct 213 ms 53380 KB Output is correct
14 Correct 210 ms 53352 KB Output is correct
15 Correct 211 ms 53396 KB Output is correct
16 Correct 209 ms 53488 KB Output is correct
17 Correct 195 ms 52748 KB Output is correct
18 Correct 194 ms 52968 KB Output is correct
19 Correct 701 ms 117200 KB Output is correct
20 Correct 705 ms 117144 KB Output is correct
21 Correct 715 ms 117320 KB Output is correct
22 Correct 721 ms 117148 KB Output is correct
23 Correct 704 ms 117276 KB Output is correct
24 Correct 732 ms 117148 KB Output is correct