Submission #586684

#	Time	Username	Problem	Language	Result	Execution time	Memory
586684		M_W	Park (BOI16_park)	C++17	0 / 100	254 ms	33336 KiB

park

#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 (stderr)

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
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42