Submission #103308

#	Time	Username	Problem	Language	Result	Execution time	Memory
103308		pavel	Park (BOI16_park)	C++14	27 / 100	520 ms	66164 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;

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

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() && 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 (stderr)

park.cpp: In function 'int main()':
park.cpp:49: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:51:14: 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:64:14: 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: 0 / 31
• Subtask 3: 0 / 42