답안 #99390

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
99390 2019-03-03T12:33:07 Z dantoh000 Park (BOI16_park) C++14
100 / 100
556 ms 50108 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;
int numedges = 0;
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;
    numedges++;
    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;
    }
}
int finder(int a, int b){
    if (a > b) swap(a,b);
    if (a == 0 && b == 1) return 0;
    if (a == 0 && b == 2) return 1;
    if (a == 0 && b == 3) return 2;
    if (a == 1 && b == 2) return 3;
    if (a == 1 && b == 3) return 4;
    if (a == 2 && b == 3) return 5;
}
main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //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[6];
    b[0] = b[1] = b[2] = b[3] = b[4] = b[5] = true;
    int thres[6];
    for (auto cur : edgelist){
        int d = cur.first, x = cur.second.first, y = cur.second.second;
        //if (!sameset(x,y)) printf("%lld %lld %lld\n",d,x,y);
        unionset(x,y);
        if (b[0] && (sameset(n,n+1) || sameset(n+1,n+3) || sameset(n+1,n+2))){
            b[0] = false;
            thres[0] = d;
        }
        if (b[1] && (sameset(n,n+1) || sameset(n+1,n+3) || sameset(n+2,n+3) || sameset(n,n+2))){
            b[1] = false;
            thres[1] = d;
        }
        if (b[2] && (sameset(n,n+1) || sameset(n,n+2) || sameset(n,n+3))){
            b[2] = false;
            thres[2] = d;
        }
        if (b[3] && (sameset(n+2,n+1) || sameset(n+2,n) || sameset(n+2,n+3))){
            b[3] = false;
            thres[3] = d;
        }
        if (b[4] && (sameset(n+2,n+1) || sameset(n+1,n+3) || sameset(n,n+3) || sameset(n,n+2))){
            b[4] = false;
            thres[4] = d;
        }
        if (b[5] && (sameset(n+3,n) || sameset(n+3,n+1) || sameset(n+3,n+2))){
            b[5] = false;
            thres[5] = d;
        }
    }
    for (int i = 0; i < 6; i++){
        //printf("%lld ", thres[i]);
    }
    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++){
            //printf("%lld %lld %lld\n",e,i,finder(e,i));
            if (e == i  || r <= thres[finder(e,i)]){
                printf("%lld",i+1);
            }
        }
        printf("\n");
    }
}

Compilation message

park.cpp:61:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
park.cpp: In function 'long long int dist(long long int, long long int)':
park.cpp:51:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
park.cpp: In function 'long long int finder(long long int, long long int)':
park.cpp:60:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
park.cpp: In function 'int main()':
park.cpp:65: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:68: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:117:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld",&r,&e);
         ~~~~~^~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 499 ms 49844 KB Output is correct
2 Correct 487 ms 49760 KB Output is correct
3 Correct 510 ms 49884 KB Output is correct
4 Correct 497 ms 49884 KB Output is correct
5 Correct 473 ms 49728 KB Output is correct
6 Correct 493 ms 49920 KB Output is correct
7 Correct 514 ms 49752 KB Output is correct
8 Correct 506 ms 49884 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 1396 KB Output is correct
2 Correct 54 ms 1280 KB Output is correct
3 Correct 54 ms 1280 KB Output is correct
4 Correct 63 ms 2420 KB Output is correct
5 Correct 67 ms 2420 KB Output is correct
6 Correct 56 ms 2420 KB Output is correct
7 Correct 50 ms 1784 KB Output is correct
8 Correct 50 ms 1788 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 499 ms 49844 KB Output is correct
2 Correct 487 ms 49760 KB Output is correct
3 Correct 510 ms 49884 KB Output is correct
4 Correct 497 ms 49884 KB Output is correct
5 Correct 473 ms 49728 KB Output is correct
6 Correct 493 ms 49920 KB Output is correct
7 Correct 514 ms 49752 KB Output is correct
8 Correct 506 ms 49884 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 56 ms 1396 KB Output is correct
12 Correct 54 ms 1280 KB Output is correct
13 Correct 54 ms 1280 KB Output is correct
14 Correct 63 ms 2420 KB Output is correct
15 Correct 67 ms 2420 KB Output is correct
16 Correct 56 ms 2420 KB Output is correct
17 Correct 50 ms 1784 KB Output is correct
18 Correct 50 ms 1788 KB Output is correct
19 Correct 527 ms 50076 KB Output is correct
20 Correct 522 ms 50012 KB Output is correct
21 Correct 555 ms 50108 KB Output is correct
22 Correct 527 ms 50096 KB Output is correct
23 Correct 530 ms 50012 KB Output is correct
24 Correct 556 ms 50012 KB Output is correct