제출 #476437

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

park

#include <bits/stdc++.h>
#define db double
using namespace std;
const int maxN = 2505;
struct tree{
    int x,y,r;
    tree(){};
}a[maxN];
struct vis{
    int r, e, id;
    bool ans[5][5];
    vis() {};
}b[maxN];
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/2)); //Bottom
        edge[++cnt] = e(i,N+2,(db)(w-a[i].x)/2); //Right
        edge[++cnt] = e(i,N+3,(db)(h-a[i].y)/2); //Top
        edge[++cnt] = e(i,N+4,(db)(a[i].x/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;
    cnt = 0;
    for(int i = 1; i <= M; ++i){
        while(edge[++cnt].w < b[i].r){
            merge(edge[cnt].from,edge[cnt].to);
        }
        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: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42