oj.uz

답안 #219884

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
219884 2020-04-06T16:13:57 Z nicolaalexandra Park (BOI16_park) C++14
0 / 100
 1830 ms 17404 KB 
#include <bits/stdc++.h>
#define DIM 2010
#define INF 1000000000
using namespace std;
struct tree{
    int x,y,r;
};
tree v[DIM];
vector <int> L[DIM];
deque <int> d;
int a[5][5],viz[DIM];
int n,m,i,j,x,y,r,c,w,h;
int overlap (int i, int val, int c){
    if (c == 1){
        if (v[i].x - v[i].r - val <= 0)
            return 1;
    } else {
        if (c == 2){
            if (v[i].y - v[i].r - val <= 0)
                return 1;
        } else {
            if (c == 3){
                if (v[i].x + v[i].r + val >= w)
                    return 1;
            } else {
                if (v[i].y + v[i].r + val >= h)
                    return 1;
            }}}
    return 0;
}
int intersectie (int x, int y, int r, int x2, int y2, int r2){
    if (1LL * (r + r2) * (r + r2) > 1LL * (x - x2) * (x - x2) + 1LL * (y - y2) * (y - y2))
        return 1;
    return 0;
}
int verif (int val, int c1, int c2){

    for (int i=1;i<=n;i++)
        L[i].clear();

    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++){
            if (intersectie (v[i].x,v[i].y,v[i].r + val, v[j].x,v[j].y,v[j].r + val)){
                L[i].push_back(j);
                L[j].push_back(i);
            }}

    /// gasesc punctele de start
    memset (viz,0,sizeof viz);
    int ok = 0;
    for (int i=1;i<=n;i++){
        if (viz[i])
            continue;

        if (!overlap(i,val,c1)) /// nu poate fi punct de start
            continue;

        d.clear();
        d.push_back(i);
        viz[i] = 1;
        while (!d.empty()){
            int nod = d.front();
            d.pop_front();
            for (auto vecin : L[nod]){
                if (!viz[vecin]){
                    d.push_back(vecin);
                    viz[vecin] = 1;
                    if (overlap(vecin,val,c2)){
                        ok = 1;
                        break;
                    }}}
            if (ok)
                break;
        }
        if (ok)
            break;
    }
    return ok;
}
int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m>>w>>h;
    for (i=1;i<=n;i++)
        cin>>v[i].x>>v[i].y>>v[i].r;

    /// raza minima cu care pot sa maresc cercurile a.i. sa blochez o bucata
    for (i=1;i<=4;i++)
        for (j=i+1;j<=4;j++){
            int st = 1, dr = INF, sol = 0;
            while (st <= dr){
                int mid = (st+dr)>>1;
                if (verif (mid,i,j)){
                    sol = mid;
                    dr = mid-1;
                } else st = mid+1;

            }
            a[i][j] = sol;
        }

    for (;m--;){
        cin>>r>>c;

        if (c == 1){

            cout<<1;

            if (!(a[1][2] <= r || a[2][4] <= r || a[2][3] <= r))
                cout<<2;

            if (!(a[1][2] <= r || a[2][4] <= r || a[3][4] <= r || a[1][3] <= r))
                cout<<3;

            if (!(a[1][2] <= r || a[1][3] <= r || a[1][4] <= r))
                cout<<4;

        } else {
            if (c == 2){

                if (!(a[1][2] <= r || a[2][4] <= r || a[2][3] <= r))
                    cout<<1;
                cout<<2;

                if (!(a[2][3] <= r || a[1][3] <= r || a[3][4] <= r))
                    cout<<3;

                if (!(a[2][3] <= r || a[1][4] <= r || a[1][3] <= r || a[2][4] <= r))
                    cout<<4;

            } else {
                if (c == 3){
                    if (!(a[1][2] <= r || a[2][4] <= r || a[3][4] <= r || a[1][3] <= r))
                        cout<<1;
                    if (!(a[2][3] <= r || a[1][3] <= r || a[3][4] <= r))
                        cout<<2;
                    cout<<3;
                    if (!(a[3][4] <= r || a[1][4] <= r || a[2][4] <= r))
                        cout<<4;
                } else { /// c == 4
                    if (!(a[1][2] <= r || a[1][3] <= r || a[1][4] <= r))
                        cout<<1;
                    if (!(a[2][3] <= r || a[1][4] <= r || a[1][3] <= r || a[2][4] <= r))
                        cout<<2;
                    if (!(a[3][4] <= r || a[1][4] <= r || a[2][4] <= r))
                        cout<<3;
                    cout<<4;
                }
            }
        }
        cout<<"\n";
    }

    return 0;
}

Subtask #1
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1804 ms 17404 KB Output is correct
2 Correct 1799 ms 17400 KB Output is correct
3 Incorrect 1830 ms 17244 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

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

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1804 ms 17404 KB Output is correct
2 Correct 1799 ms 17400 KB Output is correct
3 Incorrect 1830 ms 17244 KB Output isn't correct
4 Halted 0 ms 0 KB -