oj.uz

Submission #163709

# Submission time Handle Problem Language Result Execution time Memory
163709 2019-11-14T18:26:34 Z alexandra_udristoiu Park (BOI16_park) C++14
31 / 100
 2500 ms 17912 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 + 2 * raza > c[i].x){
            p[i] += 8;
        }
        if(c[i].r + 2 * raza > lin - c[i].x){
            p[i] += 2;
        }
        if(c[i].r + 2 * raza > c[i].y){
            p[i] += 1;
        }
        if(c[i].r + 2 * 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(113010479, 2, 3);
    for(i = 1; i <= 4; i++){
        rmax[i][i] = 1000000000;
        for(j = i + 1; j <= 4; j++){
            st = 1;
            dr = min(lin, col);
            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 2009 ms 17676 KB Output is correct
2 Correct 2031 ms 17784 KB Output is correct
3 Correct 1991 ms 17784 KB Output is correct
4 Correct 1943 ms 17912 KB Output is correct
5 Correct 1965 ms 17656 KB Output is correct
6 Correct 1979 ms 17656 KB Output is correct
7 Execution timed out 2536 ms 16632 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 2040 KB Output is correct
2 Correct 449 ms 2148 KB Output is correct
3 Correct 386 ms 1784 KB Output is correct
4 Correct 402 ms 2188 KB Output is correct
5 Correct 393 ms 2040 KB Output is correct
6 Correct 413 ms 2196 KB Output is correct
7 Correct 426 ms 1784 KB Output is correct
8 Correct 378 ms 1904 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2009 ms 17676 KB Output is correct
2 Correct 2031 ms 17784 KB Output is correct
3 Correct 1991 ms 17784 KB Output is correct
4 Correct 1943 ms 17912 KB Output is correct
5 Correct 1965 ms 17656 KB Output is correct
6 Correct 1979 ms 17656 KB Output is correct
7 Execution timed out 2536 ms 16632 KB Time limit exceeded
8 Halted 0 ms 0 KB -