oj.uz

Submission #113349

# Submission time Handle Problem Language Result Execution time Memory
113349 2019-05-25T06:43:06 Z Mahdi_Jfri Park (BOI16_park) C++14
0 / 100
 564 ms 117324 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 , {maxn , 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
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 117324 KB Output is correct
2 Correct 552 ms 117276 KB Output is correct
3 Correct 539 ms 117204 KB Output is correct
4 Correct 533 ms 117252 KB Output is correct
5 Correct 541 ms 117276 KB Output is correct
6 Correct 564 ms 117148 KB Output is correct
7 Correct 522 ms 117272 KB Output is correct
8 Incorrect 557 ms 117276 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 53436 KB Output is correct
2 Correct 225 ms 53528 KB Output is correct
3 Correct 208 ms 53384 KB Output is correct
4 Correct 207 ms 53360 KB Output is correct
5 Correct 210 ms 53392 KB Output is correct
6 Incorrect 215 ms 53488 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 117324 KB Output is correct
2 Correct 552 ms 117276 KB Output is correct
3 Correct 539 ms 117204 KB Output is correct
4 Correct 533 ms 117252 KB Output is correct
5 Correct 541 ms 117276 KB Output is correct
6 Correct 564 ms 117148 KB Output is correct
7 Correct 522 ms 117272 KB Output is correct
8 Incorrect 557 ms 117276 KB Output isn't correct
9 Halted 0 ms 0 KB -