제출 #448005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
448005		PiejanVDC	Odašiljači (COCI20_odasiljaci)	C++17	70 / 70	54 ms	16868 KiB

odasiljaci

#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 / 70