oj.uz

답안 #586709

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
586709 2022-06-30T14:43:33 Z M_W Park (BOI16_park) C++17
0 / 100
 454 ms 33296 KB 
#include <bits/stdc++.h>
#define ii pair<int, int>
#define pi pair<long long, ii>
using namespace std;
vector<pi> ed;
long long x[2020], y[2020], r[2020];
bool ans[100001][5];
int pa[2020];

long long find_dist(long long x1, long long y1, long long x2, long long y2){
	int dx = x1 - x2, dy = y1 - y2;
	long long dist = dx * dx + dy * dy;
	long long l = 0, r = 1e9;
	while(l < r){
		long long mid = (l + r + 1) >> 1;
		if(mid * mid <= dist) l = mid;
		else r = mid - 1;
	}
	return l;
}

int findpa(int a){
	return pa[a] == a ? a : pa[a] = findpa(pa[a]);
}

int main(){
	int N, Q;
	long long W, H;
	scanf("%d %d %lld %lld", &N, &Q, &W, &H);
	for(int i = 5; i <= N + 4; i++){
		scanf("%lld %lld %lld", &x[i], &y[i], &r[i]);
		for(int j = 5; j < i; j++){
			ed.push_back({find_dist(x[i], y[i], x[j], y[j]) - r[i] - r[j], {i, j}});
		}
		ed.push_back({x[i] - r[i], {i, 1}});
		ed.push_back({y[i] - r[i], {i, 2}});
		ed.push_back({W - x[i] - r[i], {i, 3}});
		ed.push_back({H - y[i] - r[i], {i, 4}});
	}
	// for(auto x : ed) printf("%lld\n", x.first);
	for(int i = 1; i <= N + 4; i++) pa[i] = i;
	sort(ed.begin(), ed.end());
	vector<pi> query;
	for(int i = 1; i <= Q; i++){
		long long rq; int e;
		scanf("%lld %d", &rq, &e);
		query.push_back({rq, {e, i}});
	}
	sort(query.begin(), query.end());
	int ptr = 0;
	for(int i = 0; i < Q; i++){
		auto [rq, tmp] = query[i];
		auto [e, q] = tmp;
		
		while(ptr < ed.size() && ed[ptr].first < rq << 1){
			pa[findpa(ed[ptr].second.first)] = findpa(ed[ptr].second.second);
			ptr++;
		}
		
		bool cn[5][5];
		for(int i = 1; i <= 4; i++){
			for(int j = 1; j <= 4; j++){
				if(j == i) continue;
				cn[i][j] = findpa(i) == findpa(j);
			}
		}
		
		int kk[4];
		for(int j = 1; j <= 3; j++){
			kk[j] = e + j;
			if(kk[j] > 4) kk[j] -= 4;
		}
		
		for(int j = 1; j <= 4; j++) ans[q][j] = true;
		if(cn[e][kk[1]] || cn[e][kk[2]] || cn[e][kk[3]]) ans[q][kk[3]] = false;
		if(cn[kk[1]][e] || cn[kk[1]][kk[2]] || cn[kk[1]][kk[3]]) ans[q][kk[1]] = false;
		if(cn[e][kk[2]] || cn[kk[1]][kk[3]] || cn[kk[2]][kk[3]] || cn[e][kk[1]]) ans[q][kk[2]] = false;
	}
	for(int i = 1; i <= Q; i++){
		for(int j = 1; j <= 4; j++){
			if(ans[i][j]) printf("%d", j);
		}
		printf("\n");
	}
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:55:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   while(ptr < ed.size() && ed[ptr].first < rq << 1){
      |         ~~~~^~~~~~~~~~~
park.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |  scanf("%d %d %lld %lld", &N, &Q, &W, &H);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |   scanf("%lld %lld %lld", &x[i], &y[i], &r[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |   scanf("%lld %d", &rq, &e);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 425 ms 33296 KB Output is correct
2 Incorrect 454 ms 33284 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 49 ms 3008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 425 ms 33296 KB Output is correct
2 Incorrect 454 ms 33284 KB Output isn't correct
3 Halted 0 ms 0 KB -