제출 #103322

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
103322		pavel	Park (BOI16_park)	C++14	100 / 100	525 ms	66940 KiB

park

    #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]);
        }
    }

컴파일 시 표준 에러 (stderr) 메시지

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 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42