oj.uz

Submission #476440

# Submission time Handle Problem Language Result Execution time Memory
476440 2021-09-26T20:36:03 Z Qw3rTy Park (BOI16_park) C++11
100 / 100
 558 ms 54396 KB 
#include <bits/stdc++.h>
#define int long long
#define db double
using namespace std;
const int maxN = 2005;
const int maxM = 1e5+5;
struct tree{
    int x,y,r;
    tree(){};
}a[maxN];
struct vis{
    int r, e, id;
    bool ans[5][5];
    vis() {};
}b[maxM];
struct e{
    int from, to; db w;
    e(){};
    e(int from, int to, int w){
        this -> from = from;
        this -> to = to;
        this -> w = w;
    }
}edge[maxN*maxN];
bool cmp1(vis a, vis b){
    return a.r < b.r;
}
bool cmp2(e a, e b){
    return a.w < b.w;
}
bool cmp3(vis a, vis b){
    return a.id < b.id;
}
db dist(int i, int j){
    return sqrt(((a[i].x-a[j].x)*(a[i].x-a[j].x))+((a[i].y-a[j].y)*(a[i].y-a[j].y)));
}
//DSU
int fa[maxN];
int find(int x){
    return x == fa[x]?x:(fa[x] = find(fa[x]));
}
void merge(int x, int y){
    int fx = find(x); int fy = find(y);
    if(fx == fy)return;
    fa[fx] = fy;
}
int N,M,w,h,cnt=0;
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen("../test.in","r",stdin);
    //Read in data
    cin >> N >> M >> w >> h;
    for(int i = 1; i <= N; ++i)cin >> a[i].x >> a[i].y >> a[i].r;
    for(int i = 1; i <= M; ++i){
        cin >> b[i].r >> b[i].e;
        b[i].id = i;
        memset(b[i].ans,true,sizeof(b[i].ans));
    }
    //Sort visitors by radius
    sort(b+1,b+M+1,cmp1);
    //建图
    //with borders
    for(int i = 1; i <= N; ++i){
        edge[++cnt] = e(i,N+1,(db)((a[i].y-a[i].r)/2)); //Bottom
        edge[++cnt] = e(i,N+2,(db)((w-a[i].x-a[i].r)/2)); //Right
        edge[++cnt] = e(i,N+3,(db)((h-a[i].y-a[i].r)/2)); //Top
        edge[++cnt] = e(i,N+4,(db)((a[i].x-a[i].r)/2)); //Left
    }
    //with other points
    for(int i = 1; i <= N; ++i){
        for(int j = i+1; j <= N; ++j){
            edge[++cnt] = e(i,j,(db)((dist(i,j)-a[i].r-a[j].r)/2));
        }
    }
    //Sort edges by weight
    sort(edge+1,edge+cnt+1,cmp2);
    //Init DSU
    for(int i = 1; i <= N+4; ++i)fa[i] = i;
    int idx = 1;
    for(int i = 1; i <= M; ++i){
        while(idx < cnt && edge[idx].w < b[i].r){
            merge(edge[idx].from,edge[idx].to);
            ++idx;
        }
        if(find(N+1) == find(N+2)){
            b[i].ans[1][2] = b[i].ans[2][3] = b[i].ans[2][4] = false;
        }
        if(find(N+1) == find(N+3)){
            b[i].ans[1][2] = b[i].ans[1][3] = b[i].ans[2][4] = b[i].ans[3][4] = false;
        }
        if(find(N+1) == find(N+4)){
            b[i].ans[1][2] = b[i].ans[1][3] = b[i].ans[1][4] = false;
        }
        if(find(N+2) == find(N+3)){
            b[i].ans[1][3] = b[i].ans[2][3] = b[i].ans[3][4] = false;
        }
        if(find(N+2) == find(N+4)){
            b[i].ans[1][3] = b[i].ans[1][4] = b[i].ans[2][3] = b[i].ans[2][4] = false;
        }
        if(find(N+3) == find(N+4)){
            b[i].ans[1][4] = b[i].ans[2][4] = b[i].ans[3][4] = false;
        }
    }
    sort(b+1,b+M+1,cmp3);
    for(int i = 1; i <= M; ++i){
        for(int j = 1; j <= 4; ++j){
            if(b[i].ans[min(b[i].e,j)][max(b[i].e,j)] == true){
                cout << j;
            }
        }
        cout << '\n';
    }
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 47492 KB Output is correct
2 Correct 518 ms 47492 KB Output is correct
3 Correct 469 ms 47544 KB Output is correct
4 Correct 487 ms 47544 KB Output is correct
5 Correct 467 ms 47548 KB Output is correct
6 Correct 472 ms 47552 KB Output is correct
7 Correct 442 ms 47544 KB Output is correct
8 Correct 436 ms 47540 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 7500 KB Output is correct
2 Correct 99 ms 7596 KB Output is correct
3 Correct 84 ms 7620 KB Output is correct
4 Correct 105 ms 7744 KB Output is correct
5 Correct 99 ms 7604 KB Output is correct
6 Correct 85 ms 7660 KB Output is correct
7 Correct 80 ms 7224 KB Output is correct
8 Correct 82 ms 7216 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 47492 KB Output is correct
2 Correct 518 ms 47492 KB Output is correct
3 Correct 469 ms 47544 KB Output is correct
4 Correct 487 ms 47544 KB Output is correct
5 Correct 467 ms 47548 KB Output is correct
6 Correct 472 ms 47552 KB Output is correct
7 Correct 442 ms 47544 KB Output is correct
8 Correct 436 ms 47540 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 92 ms 7500 KB Output is correct
12 Correct 99 ms 7596 KB Output is correct
13 Correct 84 ms 7620 KB Output is correct
14 Correct 105 ms 7744 KB Output is correct
15 Correct 99 ms 7604 KB Output is correct
16 Correct 85 ms 7660 KB Output is correct
17 Correct 80 ms 7224 KB Output is correct
18 Correct 82 ms 7216 KB Output is correct
19 Correct 557 ms 54392 KB Output is correct
20 Correct 558 ms 54248 KB Output is correct
21 Correct 533 ms 54340 KB Output is correct
22 Correct 539 ms 54300 KB Output is correct
23 Correct 552 ms 54268 KB Output is correct
24 Correct 548 ms 54396 KB Output is correct