답안 #937450

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
937450 2024-03-04T05:36:31 Z Amaarsaa Park (BOI16_park) C++14
0 / 100
280 ms 97372 KB
#include<bits/stdc++.h>

using namespace std;
using ll = long long ;
using pll = pair < ll, ll >;
bool B[5][2002] = {false};
bool D[5][5] = {false};
int 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 < double, 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 ++) {
			double S = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
			S = sqrt(S);
			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[5];
	ind= 0;
	for (pair < ll, pair < ll, ll > >& P : Q) {
		double 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();
					R = Get(Pa.first);
					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() && v[ind].first < S) {
			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 = 1;
			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 <= m; i ++) {
		cout << Ans[i] << endl;
	}
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:81:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<double, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   while ( ind < v.size() && v[ind].first < S) {
      |           ~~~~^~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Runtime error 280 ms 97372 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 50 ms 7492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 280 ms 97372 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -