Submission #1263498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263498		Roupiq	Circle selection (APIO18_circle_selection)	C++20	15 / 100	3094 ms	25884 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> p, sz;
    DSU(int n): p(n), sz(n,1){ iota(p.begin(), p.end(), 0); }
    int find(int a){ return p[a]==a?a:p[a]=find(p[a]); }
    void unite(int a,int b){
        a=find(a); b=find(b);
        if(a==b) return;
        if(sz[a]<sz[b]) swap(a,b);
        p[b]=a; sz[a]+=sz[b];
    }
};

struct Circle {
    long long x,y,r;
    int id;
};

inline bool intersect(const Circle&a,const Circle&b){
    __int128 dx=a.x-b.x;
    __int128 dy=a.y-b.y;
    __int128 dist2=dx*dx+dy*dy;
    __int128 sum=a.r+b.r;
    return dist2 <= sum*sum;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin>>n;
    vector<Circle> c(n);
    for(int i=0;i<n;i++){
        cin>>c[i].x>>c[i].y>>c[i].r;
        c[i].id=i;
    }

    struct Event{
        long long x; int id; bool enter;
    };
    vector<Event> ev;
    ev.reserve(2*n);
    for(auto &ci:c){
        ev.push_back({ci.x-ci.r, ci.id, true});
        ev.push_back({ci.x+ci.r, ci.id, false});
    }
    sort(ev.begin(), ev.end(), [](auto&a,auto&b){
        if(a.x!=b.x) return a.x<b.x;
        return a.enter > b.enter; // wejście przed wyjściem
    });

    DSU dsu(n);

    // aktywne: posortowane po y
    set<pair<long long,int>> active;

    for(auto&e:ev){
        int id=e.id;
        if(e.enter){
            // sprawdzamy kolizje tylko z sąsiadami w pobliżu Y
            // (tu uproszczone: sprawdzamy wszystkich aktywnych)
            for(auto [y,j]:active){
                if(intersect(c[id], c[j])) dsu.unite(id,j);
            }
            active.insert({c[id].y,id});
        } else {
            active.erase({c[id].y,id});
        }
    }

    // znajdź lidera każdej składowej
    vector<int> leader(n);
    for(int i=0;i<n;i++) leader[dsu.find(i)]=i;
    for(int i=0;i<n;i++){
        int r=dsu.find(i);
        int j=leader[r];
        if(c[i].r>c[j].r || (c[i].r==c[j].r && c[i].id< c[j].id))
            leader[r]=i;
    }

    // odpowiedzi
    vector<int> ans(n);
    for(int i=0;i<n;i++)
        ans[i]=leader[dsu.find(i)]+1;

    for(int i=0;i<n;i++){
        if(i) cout<<" ";
        cout<<ans[i];
    }
    cout<<"\n";
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 12
• Subtask 3: 15 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13