Submission #1152335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152335		zhehan	Odašiljači (COCI20_odasiljaci)	C++20	70 / 70	113 ms	12716 KiB

odasiljaci

#include <bits/stdc++.h>

using namespace std;

#define int long long

typedef pair<int,int> ii;
typedef pair<int,ii> dii;

int dist(ii a, ii b){
    return (int)(pow(((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second)),0.5)*1e9);
}

vector<int> ufds;

int search(int p){
    if(ufds[p]==-1){
        return p;
    }
    return ufds[p] = search(ufds[p]);
}

void join(int a, int b){
    ufds[search(a)] = search(b);
}

signed main(){
    int n;
    cin>>n;
    vector<ii> antenna(n,ii());
    ufds = vector<int> (n,-1);
    for (int i=0;i<n;++i){
        cin>>antenna[i].first>>antenna[i].second;
    }
    priority_queue<dii,vector<dii>,greater<dii>> mst;
    for(int i=0;i<n;++i){
        for (int j=i+1;j<n;++j){
            if(i!=j) mst.push(dii(dist(antenna[i],antenna[j]),ii(i,j)));
        }
    }
    double max_dist = 0;
    while(!mst.empty()){
        auto curr = mst.top();
        mst.pop();
        double dist=curr.first;
        int a = curr.second.first, b = curr.second.second;
        if(search(a)==search(b)) continue;
        join(a,b);
        max_dist = max(max_dist, dist);
    }
    cout<<fixed;
    cout<<setprecision(9);
    cout<<max_dist/2000000000;
}

• Subtask 1: 70 / 70