oj.uz

Submission #586684

# Submission time Handle Problem Language Result Execution time Memory
586684 2022-06-30T14:34:58 Z M_W Park (BOI16_park) C++17
0 / 100
 254 ms 33336 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){
	double dx = double(x1 - x2), dy = double(y1 - y2);
	double dist = sqrt(dx * dx + dy * dy);
	return (long long)(dist);
}

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(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:48: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]
   48 |   while(ptr < ed.size() && ed[ptr].first < rq << 1){
      |         ~~~~^~~~~~~~~~~
park.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%d %d %lld %lld", &N, &Q, &W, &H);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   scanf("%lld %lld %lld", &x[i], &y[i], &r[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |   scanf("%lld %d", &rq, &e);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 33296 KB Output is correct
2 Correct 244 ms 33336 KB Output is correct
3 Correct 245 ms 33272 KB Output is correct
4 Correct 246 ms 33316 KB Output is correct
5 Correct 238 ms 33312 KB Output is correct
6 Correct 235 ms 33216 KB Output is correct
7 Correct 235 ms 33252 KB Output is correct
8 Correct 251 ms 33264 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Incorrect 0 ms 212 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 3100 KB Output is correct
2 Correct 58 ms 3132 KB Output is correct
3 Correct 59 ms 3088 KB Output is correct
4 Correct 57 ms 3108 KB Output is correct
5 Correct 57 ms 3056 KB Output is correct
6 Correct 85 ms 3192 KB Output is correct
7 Incorrect 59 ms 2700 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 33296 KB Output is correct
2 Correct 244 ms 33336 KB Output is correct
3 Correct 245 ms 33272 KB Output is correct
4 Correct 246 ms 33316 KB Output is correct
5 Correct 238 ms 33312 KB Output is correct
6 Correct 235 ms 33216 KB Output is correct
7 Correct 235 ms 33252 KB Output is correct
8 Correct 251 ms 33264 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Incorrect 0 ms 212 KB Output isn't correct
11 Halted 0 ms 0 KB -