oj.uz

Submission #792342

# Submission time Handle Problem Language Result Execution time Memory
792342 2023-07-25T01:47:58 Z 1075508020060209tc Odašiljači (COCI20_odasiljaci) C++14
70 / 70
 263 ms 356 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
//#pragma GCC target("popcnt")
using namespace std;
#define int long long
int n;
int ar[500005];
int br[500005];
int uf[500005];

int fin(int x){
if(uf[x]==x){return x;}
uf[x]=fin(uf[x]);
return uf[x];
}
void mrg(int a,int b){
int pa=fin(a);int pb=fin(b);
if(pa==pb){return;}
uf[pa]=pb;
}

double dst(int i,int j){
int a=ar[i]-ar[j];int b=br[i]-br[j];
return sqrt(a*a+b*b);
}


int ok(double mi){
for(int i=1;i<=n;i++){
    uf[i]=i;
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        if(dst(i,j)<mi+mi){
            mrg(i,j);
        }
    }
}
for(int i=1;i<=n;i++){
    if(fin(i)!=fin(1)){return 0;}
}
return 1;
}

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>ar[i]>>br[i];
    }
    double l=0;double r=1000000000;
    for(int i=1;i<=80;i++){
        double mi=(l+r)/2;
        if(ok(mi)){
            r=mi;
        }else{
            l=mi;
        }
    }
    cout<<fixed<<setprecision(7)<<l;
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 3 ms 212 KB Output is correct
6 Correct 74 ms 320 KB Output is correct
7 Correct 78 ms 308 KB Output is correct
8 Correct 167 ms 340 KB Output is correct
9 Correct 263 ms 348 KB Output is correct
10 Correct 260 ms 356 KB Output is correct