Submission #1152271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152271		zhehan	Odašiljači (COCI20_odasiljaci)	C++20	21 / 70	128 ms	16796 KiB

odasiljaci

#include <bits/stdc++.h>

using namespace std;

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

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

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);
}

int 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=0;j<n;++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<<max_dist/2;
}

• Subtask 1: 21 / 70