oj.uz

답안 #258529

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
258529 2020-08-06T05:40:09 Z 반딧불(#5073) Park (BOI16_park) C++17
0 / 100
 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;
                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 27.0

# 결과 실행 시간 메모리 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 -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 72 ms 9456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 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 -