oj.uz

Submission #448005

# Submission time Handle Problem Language Result Execution time Memory
448005 2021-07-28T13:22:53 Z PiejanVDC Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 54 ms 16868 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int>parent;

int UF(int u) {
    if(parent[u] == u) return u;
    return parent[u] = UF(parent[u]);
}

signed main() {
    int n; cin>>n;
    parent.resize(n);
    for(int i = 0 ; i < n ; i++) parent[i]=i;
    vector<pair<int64_t,int64_t>>v(n);
    for(auto &z : v) cin>>z.first>>z.second;
    priority_queue<pair<long double,pair<int,int>>>pq;
    for(int i = 0 ; i < n-1 ; i++) {
        for(int j = i+1 ; j < n ; j++) {
            long long a = abs(v[i].first-v[j].first),b = abs(v[i].second-v[j].second);
            long double temp = (sqrt(a*a + b*b))/2;
            pq.push({-temp,{i,j}});
        }
    }
    int cnt = 0;
    long double ans;
    while(true) {
        int a = pq.top().second.first, b = pq.top().second.second;
        int p1 = UF(a), p2 = UF(b);
        if(p1 != p2) {
            cnt++;
            if(cnt == n-1) {
                ans=-pq.top().first;
                break;
            }
            parent[p1]=p2;
        }
        pq.pop();
    }
    cout << fixed << setprecision(8) << ans;
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 13 ms 4540 KB Output is correct
7 Correct 13 ms 4540 KB Output is correct
8 Correct 34 ms 16780 KB Output is correct
9 Correct 54 ms 16780 KB Output is correct
10 Correct 53 ms 16868 KB Output is correct