Submission #468301

#	Time	Username	Problem	Language	Result	Execution time	Memory
468301		Marceantasy	Odašiljači (COCI20_odasiljaci)	C++17	70 / 70	73 ms	8632 KiB

odasiljaci

#include <bits/stdc++.h>
using namespace std; 

#define ll long long; 
#define ar array; 

const int mxN = 1010, M = 1e9+7; 
int n, p[mxN]; 
pair<int, int> a[mxN];

int find_set(int a){
    if(a == p[a]){
        return a; 
    }
    return p[a] = find_set(p[a]);
}

void union_set(int a, int b){
    a = find_set(a); 
    b = find_set(b); 
    assert(a != b);
    p[b] = a;
}

double euclidean(pair<int, int> f, pair<int, int> t){
    return sqrt((double)((double)(t.first-f.first) * (double)(t.first-f.first)) + (double)((double)(t.second-f.second) * (double)(t.second-f.second)));
}

int main(){
    cout << fixed << setprecision(8);
    cin >> n;
    iota(p, p+n, 0);  
    for(int i = 0; i<n; ++i){
        cin >> a[i].first >> a[i].second;
    }
    vector<pair<double, pair<int, int>>> distances;
    for(int i = 0; i<n; ++i){
        for(int j = i+1; j<n; ++j){
            distances.push_back(make_pair(euclidean(a[i], a[j]) / 2, make_pair(i, j)));
        }
    }
    double ans = 0;
    sort(distances.begin(), distances.end());
    for(auto it : distances){
        if(find_set(it.second.first) != find_set(it.second.second)){
            union_set(it.second.first, it.second.second);
            ans = it.first;
        }
    }
    cout << ans << "\n";
}

• Subtask 1: 70 / 70