oj.uz

Submission #336185

# Submission time Handle Problem Language Result Execution time Memory
336185 2020-12-15T01:19:16 Z wiwiho Odašiljači (COCI20_odasiljaci) C++14
70 / 70
 69 ms 8668 KB 
#include<bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define lsort(a) sort(iter(a))
#define eb emplace_back

using namespace std;

typedef long long ll;

vector<int> dsu;

int findDSU(int a){
    if(dsu[a] != a) dsu[a] = findDSU(dsu[a]);
    return dsu[a];
}

void unionDSU(int a, int b){
    a = findDSU(a);
    b = findDSU(b);
    dsu[b] = a;
}

ll dis(pll a, pll b){
    ll x = a.F - b.F;
    ll y = a.S - b.S;
    return x *x + y * y;
}

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

    int n;
    cin >> n;

    vector<pll> p(n);
    for(int i =0 ; i < n; i++) cin >> p[i].F >> p[i].S;

    vector<pair<ll, pii>> e;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++) e.eb(mp(dis(p[i], p[j]), mp(i, j)));
    }

    lsort(e);

    dsu.resize(n);
    for(int i = 0; i < n; i++) dsu[i] = i;

    ll ans = 0;
    for(auto i : e){
        if(findDSU(i.S.F) == findDSU(i.S.S)) continue;
        ans = i.F;
        unionDSU(i.S.F, i.S.S);
    }

    cout << fixed << setprecision(20) << sqrt(ans) / 2 << "\n";

    return 0;
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 20 ms 2532 KB Output is correct
7 Correct 19 ms 2660 KB Output is correct
8 Correct 47 ms 8668 KB Output is correct
9 Correct 69 ms 8668 KB Output is correct
10 Correct 68 ms 8668 KB Output is correct