oj.uz

Submission #99387

# Submission time Handle Problem Language Result Execution time Memory
99387 2019-03-03T11:58:34 Z dantoh000 Park (BOI16_park) C++14
0 / 100
 545 ms 50060 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
vector<iii> a;
int n,m,w,h;
vi p,rk;
void init(int n){
    for (int i = 0; i < n; i++){
        p.push_back(i);
        rk.push_back(0);
    }
}
int findset(int x){
    return x == p[x] ? x : p[x] = findset(p[x]);
}
bool sameset(int x, int y){
    return findset(x) == findset(y);
}
void unionset(int i, int j){
    int x = findset(i);
    int y=  findset(j);
    if (x == y) return;
    if (rk[x] < rk[y]){
        p[x] =y;
    }
    else{
        p[y] = x;
        if (rk[x] == rk[y]) rk[x]++;
    }
}
int sqrt(int x){
    return (int)(pow(x,0.50000000));
}
int dist(int i, int j){
    int r = a[i].first, x = a[i].second.first, y = a[i].second.second;
    if (j >= n){
        if (j == n) return x-r;
        if (j == n+1) return y-r;
        if (j == n+2) return w-x-r;
        if (j == n+3) return h-y-r;
    }
    else{
        int r1 = a[j].first, x1 = a[j].second.first, y1 = a[j].second.second;
        return sqrt((x1-x)*(x1-x)+(y1-y)*(y1-y)) - r1-r;
    }
}
main(){
    //freopen("testdebug.txt","w",stdout);
    scanf("%lld%lld%lld%lld",&n,&m,&w,&h);
    for (int i = 0; i < n; i++){
        int x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        a.push_back(iii(z,ii(x,y)));
    }
    vector<iii> edgelist;
    for (int i = 0; i < n; i++){
        for (int j = i+1; j < n+4; j++){
            //printf("dist from %lld %lld = %lld\n",i,j,dist(i,j));
            edgelist.push_back(iii(dist(i,j),ii(i,j)));
        }
    }
    sort(edgelist.begin(),edgelist.end());
    init(n+4);
    bool b[4];
    b[0] = b[1] = b[2] = b[3] = true;
    int thres[4];
    for (auto cur : edgelist){
        int d = cur.first, x = cur.second.first, y = cur.second.second;
        unionset(x,y);
        for (int i = 0; i < 4; i++){
            if (b[i] && sameset(n+i,n+(i+1)%4)){
                b[i] = false;
                thres[i] = d;
            }
        }
    }
    for (int i = 0; i < m; i++){
        int r,e;
        scanf("%lld%lld",&r,&e);
        r *= 2;
        e--;
        for (int i = 0; i < 4; i++){
            if (e == i  || thres[i] >= r && thres[e] >= r){
                printf("%lld",i+1);
            }
        }
        printf("\n");
    }
}

Compilation message

park.cpp:50:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
park.cpp: In function 'int main()':
park.cpp:86:42: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
             if (e == i  || thres[i] >= r && thres[e] >= r){
                            ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
park.cpp: In function 'long long int dist(long long int, long long int)':
park.cpp:49:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
park.cpp: In function 'int main()':
park.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld%lld%lld",&n,&m,&w,&h);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld",&x,&y,&z);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld",&r,&e);
         ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 49756 KB Output is correct
2 Correct 509 ms 49884 KB Output is correct
3 Correct 545 ms 50060 KB Output is correct
4 Correct 504 ms 49988 KB Output is correct
5 Correct 486 ms 49884 KB Output is correct
6 Correct 513 ms 49884 KB Output is correct
7 Incorrect 476 ms 49760 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 1348 KB Output is correct
2 Correct 54 ms 1280 KB Output is correct
3 Incorrect 97 ms 1396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 49756 KB Output is correct
2 Correct 509 ms 49884 KB Output is correct
3 Correct 545 ms 50060 KB Output is correct
4 Correct 504 ms 49988 KB Output is correct
5 Correct 486 ms 49884 KB Output is correct
6 Correct 513 ms 49884 KB Output is correct
7 Incorrect 476 ms 49760 KB Output isn't correct
8 Halted 0 ms 0 KB -