제출 #476440

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
476440		Qw3rTy	Park (BOI16_park)	C++11	100 / 100	558 ms	54396 KiB

park

#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 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42