Submission #334595

#	Time	Username	Problem	Language	Result	Execution time	Memory
334595		achibasadzishvili	Odašiljači (COCI20_odasiljaci)	C++14	70 / 70	63 ms	8800 KiB

odasiljaci

#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 (stderr)

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 / 70