Submission #937460

#	Time	Username	Problem	Language	Result	Execution time	Memory
937460		Amaarsaa	Park (BOI16_park)	C++14	100 / 100	367 ms	59092 KiB

park

#include<bits/stdc++.h>

using namespace std;
using ll = long long ;
using pll = pair < ll, ll >;
bool B[5][4002] = {false};
bool D[5][5] = {false};
ll ataman[2002];
ll Get(ll x) {
	if ( x == ataman[x]) return x;
	return ataman[x] = Get(ataman[x]);
}
void Unite(int x, int y) {
	x = Get(x);
	y = Get(y);
	if ( x == y) return ;
	ataman[x] = y;
	for ( int i = 1; i <= 4; i ++) B[i][y] |= B[i][x];
	for (int j = 1; j <= 4; j ++) {
		for (int i1 = j + 1; i1 <= 4; i1 ++) {
			if ( B[j][y] && B[i1][y]) D[j][i1] = 1;
		}
	}
	return ;
}
ll x[2002], y[2002], r[2002];
priority_queue < pll , vector <pll> , greater<pll>  > Durvuntal[5];
int main() {
	ll n, m, i, j, N, M, x1, Y, y1, R, ind, i1, ans;
	
	cin >> n >> m;
	cin >> N >> M;
	
	for (i = 1; i <= n; i ++) ataman[i] = i;
	for (i = 1; i <= n; i ++) {
		cin >> x[i] >> y[i] >> r[i];
	}
	vector < pair <long long, pair < ll, ll> > > v;
	
	for (i = 1; i <= n; i ++) {
		Durvuntal[1].push({y[i] - r[i], i});
		Durvuntal[2].push({N - (x[i] + r[i]), i});
		Durvuntal[3].push({M - (y[i] + r[i]), i});
		Durvuntal[4].push({x[i] - r[i], i});
		for (j = i+ 1; j <= n; j ++) {
			long long R = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
			long long S = sqrt(R);
			S = S - r[i] - r[j];
			v.push_back({S, {i, j}});
		}
	}
	
	sort(v.begin(), v.end());
	
	vector < pair < ll, pair < ll, ll > > > Q;
	for (i = 1; i <= m; i ++) {
		cin >> x1 >> y1;
		Q.push_back({x1, {y1, i}});
	}
	sort(Q.begin(), Q.end());
	string Ans[m + 2];
	ind= 0;
	for (pair < ll, pair < ll, ll > >& P : Q) {
		long long S = P.first * 2.0;
		for (i = 1; i <= 4; i ++) {
			while(!Durvuntal[i].empty()) {
				pll Pa = Durvuntal[i].top();
				if (Pa.first < S) {
					Durvuntal[i].pop();
		//			cout << i << " " << Pa.first << endl;
					R = Get(Pa.second);
					B[i][R] = 1;
					for (j = 1; j <= 4; j ++) {
						for (i1 = j + 1; i1 <= 4; i1 ++) {
							if ( B[j][R] && B[i1][R]) D[j][i1] = 1;
						}
					}
				}
				else break;
			}
		}
		while ( ind < v.size() ) {
			if (  v[ind].first >= S) break;
		//	cout << v[ind].first << " " << v[ind].second.first << " " << v[ind].second.second << endl;
			Unite(v[ind].second.first, v[ind].second.second);
			ind ++;
		}
		Y = P.second.first;
		if ( Y == 1) {
			ans = 1;
			if ( !D[1][4] && !D[1][2] && !D[1][3]) ans = ans * 10 + 2;
			if ( !D[1][4] && !D[2][3] && !D[1][3] && !D[2][4]) ans = ans * 10 + 3;
			if ( !D[1][4] && !D[3][4] && !D[2][4]) ans = ans * 10 + 4;
		}
		if ( Y == 2) {
			ans = 2;
			if ( !D[1][4] && !D[1][2] && !D[1][3]) ans = ans * 10 + 1;
			if ( !D[1][2] && !D[2][3] && !D[2][4]) ans = ans * 10 + 3;
			if ( !D[1][2] && !D[3][4] && !D[2][4] && !D[1][3]) ans = ans * 10 + 4;
		}
		if ( Y == 3) {
			ans = 3;
			if ( !D[1][4] && !D[2][3] && !D[1][3] && !D[2][4]) ans = ans * 10 + 1;
			if ( !D[1][2] && !D[2][3] && !D[2][4]) ans = ans * 10 + 2;
			if ( !D[2][3] && !D[3][4] && !D[1][3]) ans = ans * 10 + 4;
		}
		if ( Y == 4) {
			ans = 4;
			if ( !D[1][4] && !D[3][4] && !D[2][4]) ans = ans * 10 + 1;
			if ( !D[1][2] && !D[3][4] && !D[2][4] && !D[1][3]) ans = ans * 10 + 2;
			if ( !D[2][3] && !D[3][4] && !D[1][3]) ans = ans * 10 + 3;
		}
		string str = to_string(ans);
		sort(str.begin(), str.end());
		Ans[P.second.second] = str;
		/*
		for (i = 1; i <= 4; i ++) {
			for (j = i + 1; j <= 4; j ++) {
				cout << D[i][j] << " ";
			}
			cout << endl;
		}
		*/
	} 
	for (i = 1; i <= m; i ++) {
		cout << Ans[i] << endl;
	}
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:82:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   while ( ind < v.size() ) {
      |           ~~~~^~~~~~~~~~

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