oj.uz

Submission #872040

# Submission time Handle Problem Language Result Execution time Memory
872040 2023-11-12T07:35:04 Z aeg Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 45 ms 17852 KB 
#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.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 728 KB Output is correct
6 Correct 12 ms 4632 KB Output is correct
7 Correct 13 ms 6348 KB Output is correct
8 Correct 28 ms 17300 KB Output is correct
9 Correct 43 ms 17340 KB Output is correct
10 Correct 45 ms 17852 KB Output is correct