oj.uz

Submission #334595

# Submission time Handle Problem Language Result Execution time Memory
334595 2020-12-09T14:35:49 Z achibasadzishvili Odašiljači (COCI20_odasiljaci) C++14
70 / 70
 63 ms 8800 KB 
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
ll x[2001],y[2001],p[2005],n,sz[2005];
vector<pair<ll,pair<int,int> > >v;
ll find(ll x){
    if(p[x] == x)return x;
    return p[x] = find(p[x]);
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i=1; i<=n; i++){
        p[i] = i;
        sz[i] = 1;
        cin >> x[i] >> y[i];
    }
    
    for(int i=1; i<=n; i++){
        for(int j=i+1; j<=n; j++){
            v.pb(mp((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) , mp(i , j)));
        }
    }
    
    sort(v.begin() , v.end());
    
    for(int i=0; i<v.size(); i++){
        ll x = v[i].s.f,y=v[i].s.s;
        x = find(x);
        y = find(y);
        if(x == y)continue;
        if(sz[y] > sz[x])swap(x , y);
        sz[x] += sz[y];
        if(sz[x] == n){
            cout.precision(20);
            cout << sqrt(v[i].f)/2.0 << '\n';
            return 0;
        }
        p[y] = x;
    }
    
    
    return 0;
}

Compilation message

odasiljaci.cpp: In function 'int main()':
odasiljaci.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i=0; i<v.size(); i++){
      |                  ~^~~~~~~~~

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 544 KB Output is correct
6 Correct 18 ms 2536 KB Output is correct
7 Correct 17 ms 2536 KB Output is correct
8 Correct 43 ms 8672 KB Output is correct
9 Correct 63 ms 8800 KB Output is correct
10 Correct 61 ms 8800 KB Output is correct