oj.uz

Submission #164150

# Submission time Handle Problem Language Result Execution time Memory
164150 2019-11-17T18:22:55 Z alexandra_udristoiu Park (BOI16_park) C++14
100 / 100
 1915 ms 2168 KB 
#include<iostream>
#include<vector>
using namespace std;
int n, m, lin, col, i, j, st, dr, mid, rz, e, x;
int viz[2005], p[2005], rmax[6][6], r[2005];
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 rad(int x){
    int y = x, aux;
    while(r[x] > 0){
        x = r[x];
    }
    while(r[y] > 0){
        aux = r[y];
        r[y] = x;
        y = aux;
    }
    return x;
}
int verif(int raza, int e1, int e2){
    int i, j, r1, r2;
    for(i = 1; i <= n; i++){
        r[i] = -1;
        viz[i] = p[i] = 0;
        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) ){
                r1 = rad(i);
                r2 = rad(j);
                if(r1 != r2){
                    if(r[r1] < r[r2]){
                        p[r1] |= p[r2];
                        r[r1] += r[r2];
                        r[r2] = r1;
                    }
                    else{
                        p[r2] |= p[r1];
                        r[r2] += r[r1];
                        r[r1] = r2;
                    }
                }
            }
        }
    }
    for(i = 1; i <= n; i++){
        if(r[i] < 0){
            x = p[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>> rz >> e;
        for(i = 1; i <= 4; i++){
            if(rmax[i][e] >= rz){
                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
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1080 ms 512 KB Output is correct
2 Correct 1033 ms 632 KB Output is correct
3 Correct 1037 ms 504 KB Output is correct
4 Correct 1039 ms 536 KB Output is correct
5 Correct 1036 ms 512 KB Output is correct
6 Correct 1028 ms 544 KB Output is correct
7 Correct 1499 ms 504 KB Output is correct
8 Correct 1497 ms 604 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 2044 KB Output is correct
2 Correct 385 ms 1956 KB Output is correct
3 Correct 394 ms 1768 KB Output is correct
4 Correct 390 ms 1912 KB Output is correct
5 Correct 397 ms 1968 KB Output is correct
6 Correct 392 ms 1912 KB Output is correct
7 Correct 378 ms 1996 KB Output is correct
8 Correct 377 ms 2068 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1080 ms 512 KB Output is correct
2 Correct 1033 ms 632 KB Output is correct
3 Correct 1037 ms 504 KB Output is correct
4 Correct 1039 ms 536 KB Output is correct
5 Correct 1036 ms 512 KB Output is correct
6 Correct 1028 ms 544 KB Output is correct
7 Correct 1499 ms 504 KB Output is correct
8 Correct 1497 ms 604 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 401 ms 2044 KB Output is correct
12 Correct 385 ms 1956 KB Output is correct
13 Correct 394 ms 1768 KB Output is correct
14 Correct 390 ms 1912 KB Output is correct
15 Correct 397 ms 1968 KB Output is correct
16 Correct 392 ms 1912 KB Output is correct
17 Correct 378 ms 1996 KB Output is correct
18 Correct 377 ms 2068 KB Output is correct
19 Correct 1410 ms 2040 KB Output is correct
20 Correct 1354 ms 2040 KB Output is correct
21 Correct 1420 ms 2168 KB Output is correct
22 Correct 1329 ms 1784 KB Output is correct
23 Correct 1400 ms 1792 KB Output is correct
24 Correct 1915 ms 1884 KB Output is correct