Submission #1102657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102657		huantran	Odašiljači (COCI20_odasiljaci)	C++17	70 / 70	271 ms	52108 KiB

odasiljaci

#include <bits/stdc++.h>
// #define bit(x, i) 

using namespace std;
const int maxn = 1e3 + 5;
typedef long double ll; 

int n;
vector<tuple<ll, ll, ll>> edge;
vector<tuple<ll, ll, ll>> point;
int par[maxn];

ll dis(ll a, ll b, ll c, ll d) {
    return sqrt((a - c)*(a - c) + (b - d)*(b - d));
}

int find_par(int u) {
    return (u == par[u]) ? u : par[u] = find_par(par[u]);
}

void make_union(int u) {
    par[u] = u;
}

int merge_union(int u, int v) {
    u = find_par(u);
    v = find_par(v);

    if (u == v) {
        return false;
    }

    par[u] = v;
    return true;
}

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

    cin >> n;

    for (int i = 1; i <= n; i++) {
        make_union(i);
    }

    for (int i = 1; i <= n; i++) {
        ll a, b;
        cin >> a >> b;
        point.emplace_back(a, b, i);
    }    

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            auto [a, b, p1] = point[i];
            auto [c, d, p2] = point[j];

            ll len = dis(a, b, c, d);
            edge.emplace_back(len, p1, p2);
        }
    }

    sort(edge.begin(), edge.end());

    ll cost = 0.0;
    int num = 0;
    for (auto [w, u, v] : edge) {
        if (merge_union(u, v)) {
            cost = max(cost, w);
            num++;
        }

        if (num == n - 1)
            break;
    }

    cout << fixed << setprecision(9) << cost/2.0;
}

• Subtask 1: 70 / 70