oj.uz

Submission #103295

# Submission time Handle Problem Language Result Execution time Memory
103295 2019-03-29T17:21:58 Z pavel Park (BOI16_park) C++14
0 / 100
 310 ms 33596 KB 
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int,int> ii;

const int MAXN = 2010;
const int MAXM = 100005;

struct edge{
    double 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){
            double d = sqrt((double)(x[i]-x[j])*(x[i]-x[j])+(double)(y[i]-y[j])*(y[i]-y[j]));
            //printf("%d %d %f\n", i, j, d);
            e.emplace_back(i, j, d-r[i]-r[j]);
        }
        e.emplace_back(i, n, x[i]-r[i]);
        e.emplace_back(i, n+1, y[i]-r[i]);
        e.emplace_back(i, n+2, w-x[i]-r[i]);
        e.emplace_back(i, n+3, 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 > 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;
            }
        }
        char* s = sol[q[i].second];
        for(int j=0;j<4;++j){
            if(c[start[q[i].second]][j]){
                s+=sprintf(s, "%d", j+1);
            }
        }
    }
    for(int i=0;i<m;++i){
        puts(sol[i]);
    }
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:48: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:50: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
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 33484 KB Output is correct
2 Correct 310 ms 33340 KB Output is correct
3 Correct 292 ms 33352 KB Output is correct
4 Correct 290 ms 33596 KB Output is correct
5 Correct 299 ms 33340 KB Output is correct
6 Correct 292 ms 33512 KB Output is correct
7 Correct 287 ms 33348 KB Output is correct
8 Correct 273 ms 33388 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Incorrect 3 ms 372 KB Output isn't correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 1824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 33484 KB Output is correct
2 Correct 310 ms 33340 KB Output is correct
3 Correct 292 ms 33352 KB Output is correct
4 Correct 290 ms 33596 KB Output is correct
5 Correct 299 ms 33340 KB Output is correct
6 Correct 292 ms 33512 KB Output is correct
7 Correct 287 ms 33348 KB Output is correct
8 Correct 273 ms 33388 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Incorrect 3 ms 372 KB Output isn't correct