제출 #1293755

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1293755		trantrungkein	Park (BOI16_park)	C++20	100 / 100	356 ms	132016 KiB

park

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 1;
int n,m,w,h,x[N],y[N],r[N];
struct node{
    int u,v,w,t;
    bool operator < (const node &other) const{

        if(w != other.w) return w < other.w;
        return t < other.t;
    }
};
vector<node> edges;
vector<int> ans[N];
int sq(int x) {return x*x;}
int dist(int x, int y, int u, int v){
    return sqrt(sq(u-x) + sq(v-y));
}
void add(int x, int y,int dmm, int u, int v, int l, int r){
    int value = dist(x,y,u,v) - dmm;
    edges.push_back({l,r,value,1});
}
int par[N],siz[N];
int Find(int u){
    return (u == par[u]) ? u : par[u] = Find(par[u]);
}
void Union(int u, int v){
    u = Find(u); v = Find(v);
    if(u == v) return;
    if(siz[u] < siz[v]) swap(u,v);
    siz[u] += siz[v];
    par[v] = u;
}
int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= 2*n; i++) par[i] = i, siz[i] = 1;
    cin >> w >> h;
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i] >> r[i];
        add(x[i],y[i],r[i],0,y[i],n+1,i);
        add(x[i],y[i],r[i],x[i],h,n+2,i);
        add(x[i],y[i],r[i],w,y[i],n+3,i);
        add(x[i],y[i],r[i],x[i],0,n+4,i);
    }
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            int len = dist(x[i],y[i],x[j],y[j]) - r[i] - r[j];
            edges.push_back({i,j,len,1});
        }
    }
    for(int i = 1; i <= m; i++){
        int r,e;
        cin >> r >> e;
        edges.push_back({i,e,2*r,0});
    }
    sort(edges.begin(),edges.end());
    for(auto [u,v,w,id] :edges){
        if(id == 1){
            Union(u,v); continue;
        }
        if(v == 1){
            ans[u].push_back(v);
            if(Find(n+1) == Find(n+4)) continue;
            if(Find(n+1) != Find(n+3)){
                if(Find(n+2) != Find(n+1)) ans[u].push_back(4);
                if(Find(n+2) != Find(n+4)){
                    if(Find(n+2) != Find(n+3)) ans[u].push_back(3); }
            }
            if(Find(n+2) != Find(n+4)) {
                if(Find(n+3) != Find(n+4)) ans[u].push_back(2);
            }
        }
        if(v == 2){
            ans[u].push_back(v);
            if(Find(n+3) == Find(n+4)) continue;
            if(Find(n+1) != Find(n+3)){
                if(Find(n+2) != Find(n+3))ans[u].push_back(3);
                if(Find(n+2) != Find(n+4)){
                    if(Find(n+2) != Find(n+1)) ans[u].push_back(4); }
            }
            if(Find(n+2) != Find(n+4)) {
                if(Find(n+1) != Find(n+4)) ans[u].push_back(1);
            }
        }
        if(v == 3){
            ans[u].push_back(v);
            if(Find(n+2) == Find(n+3)) continue;
            if(Find(n+1) != Find(n+3)){
                if(Find(n+4) != Find(n+3))ans[u].push_back(2);
                if(Find(n+2) != Find(n+4)){
                    if(Find(n+1) != Find(n+4)) ans[u].push_back(1); }
            }
            if(Find(n+2) != Find(n+4)) {
                if(Find(n+1) != Find(n+2)) ans[u].push_back(4);
            }
        }
        if(v == 4){
            ans[u].push_back(v);
            if(Find(n+1) == Find(n+2)) continue;
            if(Find(n+1) != Find(n+3)){
                if(Find(n+4) != Find(n+1))ans[u].push_back(1);
                if(Find(n+2) != Find(n+4)){
                    if(Find(n+4) != Find(n+3)) ans[u].push_back(2); }
            }
            if(Find(n+2) != Find(n+4)) {
                if(Find(n+3) != Find(n+2)) ans[u].push_back(3);
            }
        }
    }
    for(int i = 1; i <= m; i++){
        sort(ans[i].begin(),ans[i].end());
        for(int id : ans[i]) cout << id; cout <<'\n';
    }
}

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42