oj.uz

Submission #468301

# Submission time Handle Problem Language Result Execution time Memory
468301 2021-08-27T14:41:54 Z Marceantasy Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 73 ms 8632 KB 
#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.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 20 ms 2496 KB Output is correct
7 Correct 20 ms 2496 KB Output is correct
8 Correct 47 ms 8632 KB Output is correct
9 Correct 72 ms 8632 KB Output is correct
10 Correct 73 ms 8632 KB Output is correct