oj.uz

Submission #1102657

# Submission time Handle Problem Language Result Execution time Memory
1102657 2024-10-18T15:04:56 Z huantran Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 271 ms 52108 KB 
#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.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 2 ms 848 KB Output is correct
5 Correct 4 ms 1360 KB Output is correct
6 Correct 77 ms 14804 KB Output is correct
7 Correct 73 ms 14804 KB Output is correct
8 Correct 177 ms 51932 KB Output is correct
9 Correct 271 ms 52108 KB Output is correct
10 Correct 269 ms 51820 KB Output is correct