oj.uz

Submission #586710

# Submission time Handle Problem Language Result Execution time Memory
586710 2022-06-30T14:44:09 Z M_W Park (BOI16_park) C++17
100 / 100
 643 ms 36300 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){
	long long 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
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 33188 KB Output is correct
2 Correct 553 ms 33288 KB Output is correct
3 Correct 555 ms 33248 KB Output is correct
4 Correct 541 ms 33228 KB Output is correct
5 Correct 576 ms 33248 KB Output is correct
6 Correct 560 ms 33260 KB Output is correct
7 Correct 532 ms 33336 KB Output is correct
8 Correct 505 ms 33200 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 3196 KB Output is correct
2 Correct 58 ms 3040 KB Output is correct
3 Correct 60 ms 3120 KB Output is correct
4 Correct 57 ms 3056 KB Output is correct
5 Correct 73 ms 3132 KB Output is correct
6 Correct 68 ms 3200 KB Output is correct
7 Correct 50 ms 2740 KB Output is correct
8 Correct 51 ms 2744 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 33188 KB Output is correct
2 Correct 553 ms 33288 KB Output is correct
3 Correct 555 ms 33248 KB Output is correct
4 Correct 541 ms 33228 KB Output is correct
5 Correct 576 ms 33248 KB Output is correct
6 Correct 560 ms 33260 KB Output is correct
7 Correct 532 ms 33336 KB Output is correct
8 Correct 505 ms 33200 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 60 ms 3196 KB Output is correct
12 Correct 58 ms 3040 KB Output is correct
13 Correct 60 ms 3120 KB Output is correct
14 Correct 57 ms 3056 KB Output is correct
15 Correct 73 ms 3132 KB Output is correct
16 Correct 68 ms 3200 KB Output is correct
17 Correct 50 ms 2740 KB Output is correct
18 Correct 51 ms 2744 KB Output is correct
19 Correct 643 ms 36164 KB Output is correct
20 Correct 630 ms 36200 KB Output is correct
21 Correct 612 ms 36272 KB Output is correct
22 Correct 596 ms 36072 KB Output is correct
23 Correct 610 ms 36300 KB Output is correct
24 Correct 589 ms 36224 KB Output is correct