제출 #163709

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
163709		alexandra_udristoiu	Park (BOI16_park)	C++14	31 / 100	2536 ms	17912 KiB

park

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 31 / 31
• Subtask 3: 0 / 42