제출 #1152276

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1152276		simuyu	Odašiljači (COCI20_odasiljaci)	C++20	35 / 70	16 ms	8624 KiB

odasiljaci

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define ii pair<int, int>
#define llii pair<ll, ii>

ll N;
ll xs[1005];
ll ys[1005];
//ll distsq[1005][1005]; // squared dists




// UFDS
int parent[1005];
int ranks[1005];

void make_set(int v) {
    parent[v] = v;
    ranks[v] = 0;
}

int find_set(int v) {
    // with path halving
    while (v != parent[v]) {
        parent[v] = parent[parent[v]];
        v = parent[v];
    }
    return v;
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        // union
        if (ranks[a] < ranks[b]) {
            // swap them
            swap(a, b);
        }
        // make parent of b be a
        parent[b] = a;
        if (ranks[a] == ranks[b]) {
            ranks[a]++;
        }
    }
}




int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // MST
    cin >> N;
    for (int i=0; i<N; i++) {
        cin >> xs[i] >> ys[i];
        make_set(i); // init UFDS
    }

    // Kruskal's algorithm for MST
    priority_queue< llii , vector<llii> , greater<llii> > kruskalpq;
    ll highestsq = 0;

    // add all edges to the pq
    for (int i=0; i<N; i++) {
        for (int j=i+1; j<N; j++) {
            kruskalpq.push(llii( (xs[i]-xs[j])*(xs[i]-xs[j]) + (ys[i]-ys[j])*(ys[i]-ys[j]) , ii(i, j) ));
            //distsq[i][j] = (xs[i]-xs[j])**2 + (ys[i]-ys[j])**2;
            //distsq[j][i] = distsq[i][j];
        }
    }

    // get MST
    ll cnt = 0; // N-1 means it's MST
    llii data;
    while (cnt < N-1) {
        data = kruskalpq.top(); kruskalpq.pop();
        //cout << "COMBINING " << data.s.f << " AND " << data.s.s << " FOR " << data.f << endl;
        if (find_set(data.s.f) == find_set(data.s.s)) {
            // already together
            //cout << "ALREADY TGT." << endl;
            continue;
        }

        // add this edge
        //cout << "UNIONED" << endl;
        union_sets(data.s.f, data.s.s);
        cnt ++;

        highestsq = data.f; // since it's bound to be higher
    }


    cout << sqrt(highestsq)/2.0 << endl; // radius will be half of this as twice transmission radius is max dist


    return 0;
}

• Subtask 1: 35 / 70