oj.uz

Submission #163699

# Submission time Handle Problem Language Result Execution time Memory
163699 2019-11-14T17:15:25 Z alexandra_udristoiu Park (BOI16_park) C++14
0 / 100
 369 ms 1644 KB 
#include<iostream>
#include<vector>
using namespace std;
int n, m, lin, col, i, j, st, dr, mid, r, e, x;
int viz[2005], p[2005], rmax[6][6];
vector<int> v[2005];
struct str{
    int x, y, r;
};
str c[2005];
void dfs(int nod){
    viz[nod] = 1;
    x |= p[nod];
    for(int i = 0; i < v[nod].size(); i++){
        if(viz[ v[nod][i] ] == 0){
            dfs(v[nod][i]);
        }
    }
}
long long pp(int x){
    return x * 1LL * x;
}
long long dist(str c1, str c2){
    return (c1.x - c2.x) * 1LL * (c1.x - c2.x) + (c1.y - c2.y) * 1LL * (c1.y - c2.y);
}
int bit(int x, int e){
    return ( (x >> e) & 1);
}
int verif(int raza, int e1, int e2){
    int i, j;
    for(i = 1; i <= n; i++){
        viz[i] = p[i] = 0;
        v[i].clear();
        if(c[i].r + raza > c[i].x){
            p[i] += 8;
        }
        if(c[i].r + raza > lin - c[i].x){
            p[i] += 2;
        }
        if(c[i].r + raza > c[i].y){
            p[i] += 1;
        }
        if(c[i].r + raza > col - c[i].y){
            p[i] += 4;
        }
    }
    for(i = 1; i < n; i++){
        for(j = i + 1; j <= n; j++){
            if( dist(c[i], c[j]) < pp(c[i].r + c[j].r + 2 * raza) ){
                v[i].push_back(j);
                v[j].push_back(i);
            }
        }
    }
    for(i = 1; i <= n; i++){
        if(viz[i] == 0){
            x = 0;
            dfs(i);
            if( bit(x, e2 - 1) && bit(x, e2 - 2) ){
                return 0;
            }
            if( bit(x, e1 - 1) && bit(x, (e1 + 2) % 4) ){
                return 0;
            }
            if( bit(x, 1) && bit(x, 3) && e1 <= 2 && e2 >= 3){
                return 0;
            }
            if( bit(x, 0) && bit(x, 2) ){
                if( (e1 == 1 && e2 != 4) || (e1 != 1 && e2 == 4) ){
                    return 0;
                }
            }
        }
    }
    return 1;
}
int main(){
    cin>> n >> m;
    cin>> lin >> col;
    for(i = 1; i <= n; i++){
        cin>> c[i].x >> c[i].y >> c[i].r;
    }
   // cout<< verif(2, 1, 4);
    for(i = 1; i <= 4; i++){
        rmax[i][i] = 100000000;
        for(j = i + 1; j <= 4; j++){
            st = 1;
            dr = min(n, m);
            while(st <= dr){
                mid = (st + dr) / 2;
                if( verif(mid, i, j) ){
                    st = mid + 1;
                }
                else{
                    dr = mid - 1;
                }
            }
            rmax[i][j] = rmax[j][i] = dr;
        }
    }
    for(; m; m--){
        cin>> r >> e;
        for(i = 1; i <= 4; i++){
            if(rmax[i][e] >= r){
                cout<< i;
            }
        }
        cout<<"\n";
    }
    return 0;
}

Compilation message

park.cpp: In function 'void dfs(int)':
park.cpp:14:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); i++){
                    ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 632 KB Output is correct
2 Incorrect 52 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 369 ms 1644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 632 KB Output is correct
2 Incorrect 52 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -