| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 258529 |
2020-08-06T05:40:09 Z |
반딧불(#5073) |
Park (BOI16_park) |
C++17 |
|
289 ms |
52164 KB |
#include <bits/stdc++.h>
#define SQR(x) ((x)*(x))
using namespace std;
typedef long long ll;
struct Query{
ll r, e; int i;
Query(){}
Query(ll r, ll e, int i): r(r), e(e), i(i){}
bool operator<(const Query &tmp)const{
return r<tmp.r;
}
};
struct Block{
ll x, y, r;
Block(){}
Block(ll x, ll y, ll r): x(x), y(y), r(r){}
bool operator<(const Block &tmp)const{
return r<tmp.r;
}
};
vector<Block> block;
inline int dir(int x){
if(x<=0) return x+4;
if(x>4) return x-4;
return x;
}
bool unq(int x, vector<int> y){
for(auto &_y: y) if(x==_y) return false;
return true;
}
bool unq(vector<int> x, vector<int> y){
for(auto &_x: x) for(auto &_y: y) if(_x==_y) return false;
return true;
}
/// corner
/// 43
/// 12
/// D: 1, R: 2, U: 3, L: 4
int n, k;
ll sx, sy;
ll x[3002], y[3002], r[3002];
Query query[100002];
vector<int> ans[100002];
int par[3002];
int find(int x){
if(par[x] == x) return x;
return par[x] = find(par[x]);
}
void merge(int x, int y){
x = find(x), y = find(y);
par[x] = y;
}
int main(){
scanf("%d %d %lld %lld", &n, &k, &sx, &sy);
for(int i=1; i<=n; i++) scanf("%lld %lld %lld", &x[i], &y[i], &r[i]), r[i]*=2;
for(int i=1; i<=n+4; i++) par[i] = i;
for(int i=1; i<=k; i++) scanf("%lld %lld", &query[i].r, &query[i].e), query[i].i=i;
sort(query+1, query+k+1);
for(int i=1; i<=n; i++){
for(int j=i+1; j<=n; j++){
ll dist = SQR(x[i]-x[j]) + SQR(y[i]-y[j]);
dist = floor(sqrt(dist)+1e-12);
dist -= r[i] + r[j];
block.push_back(Block(i, j, dist));
}
block.push_back(Block(i, n+1, y[i]-r[i]));
block.push_back(Block(i, n+2, sx-x[i]-r[i]));
block.push_back(Block(i, n+3, sy-y[i]-r[i]));
block.push_back(Block(i, n+4, x[i]-r[i]));
}
sort(block.begin(), block.end());
int pnt = 0;
for(int i=1; i<=k; i++){
while(pnt < (int)block.size() && block[pnt].r < query[i].r) merge(block[pnt].x, block[pnt].y), pnt++;
int e = query[i].e, idx = query[i].i;
ans[idx].push_back(e);
if(unq(find(n+e), {find(n+dir(e+1)), find(n+dir(e+2)), find(n+dir(e+3))})) ans[idx].push_back(dir(e+1));
if(unq(find(n+dir(e-1)), {find(n+e), find(n+dir(e+1)), find(n+dir(e+2))})) ans[idx].push_back(dir(e-1));
if(unq({find(n+dir(e-1)), find(n+dir(e-2))}, {find(n+e), find(n+dir(e+1))})) ans[idx].push_back(dir(e+2));
}
for(int i=1; i<=k; i++){
sort(ans[i].begin(), ans[i].end());
for(auto &x: ans[i]) printf("%d", x);
puts("");
}
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %lld %lld", &n, &k, &sx, &sy);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:67:73: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1; i<=n; i++) scanf("%lld %lld %lld", &x[i], &y[i], &r[i]), r[i]*=2;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
park.cpp:69:73: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1; i<=k; i++) scanf("%lld %lld", &query[i].r, &query[i].e), query[i].i=i;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
289 ms |
52164 KB |
Output is correct |
| 2 |
Incorrect |
280 ms |
52164 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
9456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
289 ms |
52164 KB |
Output is correct |
| 2 |
Incorrect |
280 ms |
52164 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
