oj.uz

Submission #219936

# Submission time Handle Problem Language Result Execution time Memory
219936 2020-04-06T17:23:12 Z nicolaalexandra Park (BOI16_park) C++14
31 / 100
 2500 ms 17528 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 - 2 * val < 0)
            return 1;
    } else {
        if (c == 2){
            if (v[i].y - v[i].r - 2 * val < 0)
                return 1;
        } else {
            if (c == 3){
                if (v[i].x + v[i].r + 2 * val > w)
                    return 1;
            } else {
                if (v[i].y + v[i].r + 2 * 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;
        if (overlap(i,val,c2)){
            ok = 1;
            break;
        }
        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 = 0, 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

# Verdict Execution time Memory Grader output
1 Correct 1803 ms 17528 KB Output is correct
2 Correct 1822 ms 17360 KB Output is correct
3 Correct 1837 ms 17220 KB Output is correct
4 Correct 1835 ms 17336 KB Output is correct
5 Correct 1797 ms 17440 KB Output is correct
6 Correct 1778 ms 17528 KB Output is correct
7 Execution timed out 2588 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 317 ms 2040 KB Output is correct
2 Correct 305 ms 2040 KB Output is correct
3 Correct 305 ms 1916 KB Output is correct
4 Correct 316 ms 2036 KB Output is correct
5 Correct 309 ms 2168 KB Output is correct
6 Correct 323 ms 2040 KB Output is correct
7 Correct 302 ms 2068 KB Output is correct
8 Correct 288 ms 1784 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1803 ms 17528 KB Output is correct
2 Correct 1822 ms 17360 KB Output is correct
3 Correct 1837 ms 17220 KB Output is correct
4 Correct 1835 ms 17336 KB Output is correct
5 Correct 1797 ms 17440 KB Output is correct
6 Correct 1778 ms 17528 KB Output is correct
7 Execution timed out 2588 ms 16632 KB Time limit exceeded
8 Halted 0 ms 0 KB -