Submission #219946

#	Time	Username	Problem	Language	Result	Execution time	Memory
219946		nicolaalexandra	Park (BOI16_park)	C++14	100 / 100	1938 ms	2040 KiB

park

#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 (int j=1;j<=n;j++){
                if (!intersectie (v[nod].x,v[nod].y,v[nod].r + val, v[j].x,v[j].y,v[j].r + val))
                    continue;
                if (!viz[j]){
                    d.push_back(j);
                    viz[j] = 1;
                    if (overlap(j,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: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42