Submission #99548

#	Time	Username	Problem	Language	Result	Execution time	Memory
99548		ShaneOng	Park (BOI16_park)	C++14	100 / 100	684 ms	132948 KiB

park

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef long double ld;
typedef pair<ld,ii> ldii;
int n,m,h,w,ans[100009][4],X[2009],Y[2009],rad[2009];
vector<ldii> edgeL;
vector<int> p,rnk;
int findS(int a){
    return a==p[a]?a:(p[a]=findS(p[a]));
}
void unionS(int a,int b){
    a=findS(a),b=findS(b);
    if(a!=b){
        if(rnk[a]<rnk[b])
            p[a]=b;
        else{
            p[b]=a;
            if(rnk[a]==rnk[b])
                rnk[a]++;
        }
    }
}
int main(){
    scanf("%d%d%d%d",&n,&m,&w,&h);
    for(int x=0;x<n;x++){
        p.push_back(x);
        rnk.push_back(0);
        scanf("%d%d%d",&X[x],&Y[x],&rad[x]);
    }
    for(int x=0;x<4;x++){
        p.push_back(n+x);
        rnk.push_back(0);
    }
    for(int x=0;x<n;x++){
        for(int y=0;y<x;y++){
            ld temp = sqrt((ld)(X[x]-X[y])*(X[x]-X[y])+(ld)(Y[x]-Y[y])*(Y[x]-Y[y]))-rad[x]-rad[y];
            edgeL.push_back(ldii(temp,ii(x,y)));
        }
    }
    for(int x=0;x<n;x++){
        edgeL.push_back(ldii((ld)h-Y[x]-rad[x],ii(x,n+3)));
        edgeL.push_back(ldii((ld)Y[x]-rad[x],ii(x,n+1)));
        edgeL.push_back(ldii((ld)w-X[x]-rad[x],ii(x,n+2)));
        edgeL.push_back(ldii((ld)X[x]-rad[x],ii(x,n)));
    }
    for(int x=0,a,b;x<m;x++){
        scanf("%d%d",&a,&b);
        edgeL.push_back(ldii((ld)2.0*a,ii(-x-1,b)));
    }
    sort(edgeL.begin(),edgeL.end());
    for(ldii edge: edgeL){
        int b=edge.second.first,a=edge.second.second;
        //printf("%Lf, %d %d\n",edge.first,a,b);
        if(b>=0){
            if(findS(a)!=findS(b)){
                unionS(a,b);
            }
        }else{
            ans[-b-1][a-1]=1;
            if(findS(n+a-1)!=findS(n+(a)%4)){
                if(findS(n+(a)%4)!=findS(n+(a+2)%4)){
                    if(findS(n+(a)%4)!=findS(n+(a+1)%4))
                        ans[-b-1][a%4]=1;

                }
                if(findS(n+a-1)!=findS(n+(a+1)%4)){
                    if(findS(n+(a)%4)!=findS(n+(a+2)%4))
                        if(findS(n+(a+2)%4)!=findS(n+(a+1)%4))
                            ans[-b-1][(a+1)%4]=1;
                    if(findS(n+(a+3)%4)!=findS(n+(a+2)%4))
                        ans[-b-1][(a+2)%4]=1;
                }
            }

        }
    }
    for(int x=0;x<m;x++){
        for(int y=0;y<4;y++){
            if(ans[x][y]==1)
                printf("%d",y+1);
        }
        printf("\n");
    }
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:25:10: 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:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&X[x],&Y[x],&rad[x]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42