oj.uz

Submission #103322

# Submission time Handle Problem Language Result Execution time Memory
103322 2019-03-29T18:19:17 Z pavel Park (BOI16_park) C++14
100 / 100
 525 ms 66940 KB 
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <vector>

    using namespace std;

    typedef pair<int,int> ii;
    typedef long double ld;

    const int MAXN = 2010;
    const int MAXM = 100005;
    const ld EPSILON = 1e-3;

    struct edge{
        ld w;
        int u,v;
        edge(int x, int y, int t){
            u=x;v=y;w=t;
        }
    };

    bool operator<(const edge& a, const edge& b){
        return a.w < b.w;
    }

    int n,m,w,h;
    int x[MAXN],y[MAXN],r[MAXN];
    int start[MAXM];
    int uf[MAXN];
    bool c[4][4];

    char sol[MAXM][10];

    int fnd(int x){
        if(uf[x]==x) return x;
        return uf[x]=fnd(uf[x]);
    }

    void un(int a, int b){
        uf[fnd(a)]=fnd(b);
    }

    bool gt(ld a, ld b){
        if(abs(a-b)<EPSILON) return false;
        return a>b;
    }

    vector<edge> e;
    vector<ii> q;

    int main(){
        for(int i=0;i<4;++i) for(int j=0;j<4;++j) c[i][j]=true;
        for(int i=0;i<MAXN;++i) uf[i]=i;
        scanf("%d%d%d%d", &n, &m, &w, &h);
        for(int i=0;i<n;++i){
            scanf("%d%d%d", &x[i], &y[i], &r[i]);
            for(int j=0;j<i;++j){
                ld d = sqrt((ld)(x[i]-x[j])*(x[i]-x[j])+(ld)(y[i]-y[j])*(y[i]-y[j]));
                e.emplace_back(i, j, d-r[i]-r[j]);
            }
            e.emplace_back(i, n, (ld)x[i]-r[i]);
            e.emplace_back(i, n+1, (ld)y[i]-r[i]);
            e.emplace_back(i, n+2, (ld)w-x[i]-r[i]);
            e.emplace_back(i, n+3, (ld)h-y[i]-r[i]);
        }
        sort(e.begin(), e.end());
        q.resize(m);
        for(int i=0;i<m;++i){
            scanf("%d%d", &q[i].first, &start[i]);
            start[i]--;
            q[i].second=i;

        }
        sort(q.begin(), q.end());
        auto it = e.begin();
        for(int i=0;i<m;++i){
            while(it!=e.end() && gt(q[i].first*2, round(it->w))){
                un(it->u, it->v);
                it++;
            }
            if(fnd(n)==fnd(n+2)){
                c[0][2]=c[0][3]=c[1][2]=c[1][3]=false;
                c[2][0]=c[3][0]=c[2][1]=c[3][1]=false;
            }
            if(fnd(n+1)==fnd(n+3)){
                c[0][1]=c[0][2]=c[3][1]=c[3][2]=false;
                c[1][0]=c[2][0]=c[1][3]=c[2][3]=false;
            }
            for(int k=0;k<4;++k){
                if(fnd(n+k)==fnd(n+(k+1)%4)){
                    for(int j=0;j<4;++j) if(k!=j) c[k][j]=c[j][k]=false;
                }
            }
            int si=0;
            for(int j=0;j<4;++j){
                if(c[start[q[i].second]][j]){
                    sol[q[i].second][si++]='1'+j;
                }
            }
        }
        for(int i=0;i<m;++i){
            puts(sol[i]);
        }
    }

Compilation message

park.cpp: In function 'int main()':
park.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &n, &m, &w, &h);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:57:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d%d", &x[i], &y[i], &r[i]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:70:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &q[i].first, &start[i]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 66204 KB Output is correct
2 Correct 476 ms 66072 KB Output is correct
3 Correct 493 ms 66200 KB Output is correct
4 Correct 515 ms 66176 KB Output is correct
5 Correct 499 ms 66152 KB Output is correct
6 Correct 517 ms 66096 KB Output is correct
7 Correct 483 ms 66196 KB Output is correct
8 Correct 451 ms 66228 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 4560 KB Output is correct
2 Correct 50 ms 4692 KB Output is correct
3 Correct 65 ms 4592 KB Output is correct
4 Correct 53 ms 4708 KB Output is correct
5 Correct 49 ms 4712 KB Output is correct
6 Correct 51 ms 4684 KB Output is correct
7 Correct 51 ms 3960 KB Output is correct
8 Correct 68 ms 3932 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 66204 KB Output is correct
2 Correct 476 ms 66072 KB Output is correct
3 Correct 493 ms 66200 KB Output is correct
4 Correct 515 ms 66176 KB Output is correct
5 Correct 499 ms 66152 KB Output is correct
6 Correct 517 ms 66096 KB Output is correct
7 Correct 483 ms 66196 KB Output is correct
8 Correct 451 ms 66228 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 47 ms 4560 KB Output is correct
12 Correct 50 ms 4692 KB Output is correct
13 Correct 65 ms 4592 KB Output is correct
14 Correct 53 ms 4708 KB Output is correct
15 Correct 49 ms 4712 KB Output is correct
16 Correct 51 ms 4684 KB Output is correct
17 Correct 51 ms 3960 KB Output is correct
18 Correct 68 ms 3932 KB Output is correct
19 Correct 514 ms 66800 KB Output is correct
20 Correct 517 ms 66692 KB Output is correct
21 Correct 486 ms 66940 KB Output is correct
22 Correct 509 ms 66636 KB Output is correct
23 Correct 525 ms 66772 KB Output is correct
24 Correct 513 ms 66900 KB Output is correct