oj.uz

답안 #219946

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
219946 2020-04-06T17:35:05 Z nicolaalexandra Park (BOI16_park) C++14
100 / 100
 1938 ms 2040 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 (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.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 634 ms 504 KB Output is correct
2 Correct 910 ms 504 KB Output is correct
3 Correct 617 ms 436 KB Output is correct
4 Correct 768 ms 384 KB Output is correct
5 Correct 875 ms 384 KB Output is correct
6 Correct 697 ms 384 KB Output is correct
7 Correct 1559 ms 440 KB Output is correct
8 Correct 1719 ms 504 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 298 ms 736 KB Output is correct
2 Correct 298 ms 888 KB Output is correct
3 Correct 299 ms 760 KB Output is correct
4 Correct 313 ms 964 KB Output is correct
5 Correct 297 ms 760 KB Output is correct
6 Correct 304 ms 760 KB Output is correct
7 Correct 293 ms 632 KB Output is correct
8 Correct 289 ms 632 KB Output is correct

Subtask #3
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 634 ms 504 KB Output is correct
2 Correct 910 ms 504 KB Output is correct
3 Correct 617 ms 436 KB Output is correct
4 Correct 768 ms 384 KB Output is correct
5 Correct 875 ms 384 KB Output is correct
6 Correct 697 ms 384 KB Output is correct
7 Correct 1559 ms 440 KB Output is correct
8 Correct 1719 ms 504 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 298 ms 736 KB Output is correct
12 Correct 298 ms 888 KB Output is correct
13 Correct 299 ms 760 KB Output is correct
14 Correct 313 ms 964 KB Output is correct
15 Correct 297 ms 760 KB Output is correct
16 Correct 304 ms 760 KB Output is correct
17 Correct 293 ms 632 KB Output is correct
18 Correct 289 ms 632 KB Output is correct
19 Correct 1191 ms 1836 KB Output is correct
20 Correct 1055 ms 2040 KB Output is correct
21 Correct 938 ms 1828 KB Output is correct
22 Correct 803 ms 1912 KB Output is correct
23 Correct 1135 ms 1784 KB Output is correct
24 Correct 1938 ms 1892 KB Output is correct