oj.uz

Submission #258536

# Submission time Handle Problem Language Result Execution time Memory
258536 2020-08-06T05:49:40 Z 반딧불(#5073) Park (BOI16_park) C++17
100 / 100
 399 ms 56184 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]);
    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].r *= 2, 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:34: 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]);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:69:90: 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].r *= 2, query[i].i=i;
                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 52140 KB Output is correct
2 Correct 283 ms 52160 KB Output is correct
3 Correct 279 ms 52164 KB Output is correct
4 Correct 280 ms 52292 KB Output is correct
5 Correct 284 ms 52144 KB Output is correct
6 Correct 280 ms 52188 KB Output is correct
7 Correct 289 ms 52168 KB Output is correct
8 Correct 269 ms 52140 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 9072 KB Output is correct
2 Correct 98 ms 9328 KB Output is correct
3 Correct 103 ms 9452 KB Output is correct
4 Correct 104 ms 9508 KB Output is correct
5 Correct 106 ms 9408 KB Output is correct
6 Correct 107 ms 9456 KB Output is correct
7 Correct 94 ms 8824 KB Output is correct
8 Correct 94 ms 8824 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 52140 KB Output is correct
2 Correct 283 ms 52160 KB Output is correct
3 Correct 279 ms 52164 KB Output is correct
4 Correct 280 ms 52292 KB Output is correct
5 Correct 284 ms 52144 KB Output is correct
6 Correct 280 ms 52188 KB Output is correct
7 Correct 289 ms 52168 KB Output is correct
8 Correct 269 ms 52140 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 114 ms 9072 KB Output is correct
12 Correct 98 ms 9328 KB Output is correct
13 Correct 103 ms 9452 KB Output is correct
14 Correct 104 ms 9508 KB Output is correct
15 Correct 106 ms 9408 KB Output is correct
16 Correct 107 ms 9456 KB Output is correct
17 Correct 94 ms 8824 KB Output is correct
18 Correct 94 ms 8824 KB Output is correct
19 Correct 374 ms 56184 KB Output is correct
20 Correct 381 ms 56184 KB Output is correct
21 Correct 399 ms 56184 KB Output is correct
22 Correct 382 ms 56184 KB Output is correct
23 Correct 365 ms 56068 KB Output is correct
24 Correct 370 ms 56112 KB Output is correct