oj.uz

답안 #935067

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
935067 2024-02-28T13:37:52 Z HossamHero7 Odašiljači (COCI20_odasiljaci) C++14
70 / 70
 66 ms 14024 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
struct dsu{
    vector<int> par;
    int comp;
    dsu(int n){
        par.resize(n);
        iota(par.begin(),par.end(),0);
        comp = n;
    }
    int getP(int node){
        if(node == par[node]) return node;
        return par[node] = getP(par[node]);
    }
    void add(int a,int b){
        a = getP(a) , b = getP(b);
        if(a == b) return;
        par[b] = a;
        comp --;
    }
};
double dis(pair<int,int> p1 , pair<int,int> p2){
    double x1 = p1.first , y1 = p1.second;
    double x2 = p2.first , y2 = p2.second;
    return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}
void solve(){
    int n;
    cin>>n;
    vector<pair<int,int>> v(n);
    for(auto &[x,y] : v) cin>>x>>y;
    vector<array<double,3>> edges;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            edges.push_back({dis(v[i],v[j])/2,(double)i,(double)j});
        }
    }
    sort(edges.begin(),edges.end());
    dsu ds(n);
    for(auto [r,a,b] : edges){
        ds.add(a,b);
        if(ds.comp == 1){
            cout<<fixed<<setprecision(6)<<r<<endl;
            return;
        }        
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message

odasiljaci.cpp: In function 'void solve()':
odasiljaci.cpp:33:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |     for(auto &[x,y] : v) cin>>x>>y;
      |               ^
odasiljaci.cpp:42:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     for(auto [r,a,b] : edges){
      |              ^

Subtask #1
70.0 / 70.0

# 결과 실행 시간 메모리 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 616 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 19 ms 4304 KB Output is correct
7 Correct 19 ms 4560 KB Output is correct
8 Correct 47 ms 14024 KB Output is correct
9 Correct 66 ms 14024 KB Output is correct
10 Correct 65 ms 13256 KB Output is correct