| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 586709 |
2022-06-30T14:43:33 Z |
M_W |
Park (BOI16_park) |
C++17 |
|
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);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
3008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
