답안 #99390 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99390	2019-03-03T12:33:07 Z	dantoh000	Park (BOI16_park)	C++14	100 / 100	556 ms	50108 KB

park

#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);
         ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

#	결과	실행 시간	메모리	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

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	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

Subtask #3
42.0 / 42.0

#	결과	실행 시간	메모리	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

답안 #99390

Compilation message

Subtask #1 27.0 / 27.0

Subtask #2 31.0 / 31.0

Subtask #3 42.0 / 42.0

Subtask #1
27.0 / 27.0

Subtask #2
31.0 / 31.0

Subtask #3
42.0 / 42.0