Submission #872040

#	Time	Username	Problem	Language	Result	Execution time	Memory
872040		aeg	Odašiljači (COCI20_odasiljaci)	C++17	70 / 70	45 ms	17852 KiB

odasiljaci

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pdpii pair<double,pair<int,int>>
vector<int> dsu;
int curu = 0;
int finddsu(int a) {
    if(dsu[a]<0) return a;
    dsu[a] = finddsu(dsu[a]);
    return dsu[a];
}
void uniondsu(int a, int b) {
    if(dsu[a]>=0) a = finddsu(a);
    if(dsu[b]>=0) b = finddsu(b);
    if(a==b) return;
    curu ++;
    if(dsu[a]<dsu[b]) {
        dsu[a] += dsu[b];
        dsu[b] = a;
    }
    else {
        dsu[b] += dsu[a];
        dsu[a] = b;
    }
}
int main(){
    int n;
    cin >> n;
    cout.precision(8);
    vector<pair<double, double>> a(n);
    priority_queue<pdpii, vector<pdpii>, greater<pdpii>> pq;
    for(int i=0; i<n; i++) cin >> a[i].F >> a[i].S;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            pq.push({sqrt((a[i].F-a[j].F)*(a[i].F-a[j].F) + (a[i].S-a[j].S)*(a[i].S-a[j].S)), {i, j}});
        }
    }
    double maxi = INT_MIN;
    dsu.assign(n,-1);
    while(curu < n-1) {
        auto a = pq.top();
        pq.pop();
        uniondsu(a.S.F,a.S.S);
        maxi = max(maxi, a.F);
    }
    cout << maxi/2 << endl;
}

• Subtask 1: 70 / 70