oj.uz

Submission #971025

# Submission time Handle Problem Language Result Execution time Memory
971025 2024-04-27T20:14:16 Z RandomUser Odašiljači (COCI20_odasiljaci) C++17
42 / 70
 1000 ms 600 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define int long long


double dist(pii x, pii y) {
    return sqrtl((x.first - y.first) * (x.first - y.first) + (x.second - y.second) * (x.second - y.second));
}

struct DSU {
    int n, comp;
    vector<int> par, size;

    void config(int _n) {
        n = _n + 1;
        comp = _n;
        par.resize(n+1);
        size.resize(n+1, 1);
        for(int i=1; i<=n; i++) par[i] = i;
    }

    int get(int u) {
        if(u == par[u]) return u;
        return par[u] = get(par[u]);
    }

    bool uni(int u, int v) {
        u = get(u), v = get(v);

        if(u == v) return false;
        if(size[u] < size[v]) swap(u, v);

        size[u] += size[v];
        par[v] = u;
        comp--;

        return true;
    }

    int getComp() { return comp; }
};

signed main() {
    int n;
    cin >> n;

    vector<pii> v(n);
    for(pii &x : v) cin >> x.first >> x.second;

    double l=0.5, r=1e12, ans=1e12;
    for(int it=0; it<120; it++) {
        double mid = (l + r) / 2;
        DSU dsu; dsu.config(n);

        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(i == j) continue;
                if(dist(v[i], v[j]) <= 2 * mid) dsu.uni(i, j);
            }
        }

        if(dsu.getComp() == 1) ans = r = mid;
        else l = mid;
    }

    cout << setprecision(8) << fixed << ans << '\n';
    return 0;
}

Subtask #1
42.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Incorrect 7 ms 436 KB Output isn't correct
5 Incorrect 19 ms 348 KB Output isn't correct
6 Correct 147 ms 344 KB Output is correct
7 Correct 153 ms 344 KB Output is correct
8 Correct 331 ms 444 KB Output is correct
9 Execution timed out 1039 ms 344 KB Time limit exceeded
10 Execution timed out 1053 ms 348 KB Time limit exceeded