Submission #1152288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152288		WongYiKai	Odašiljači (COCI20_odasiljaci)	C++20	35 / 70	190 ms	16784 KiB

odasiljaci

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	ll n;
    cin >> n;
    vector<pair<ll,ll>> v;
    for (int i=0;i<n;i++){
        ll x,y;
        cin >> x >> y;
        v.push_back({x,y});
    }
    vector<pair<ll,double>> adj[n+5];
    for (int i=0;i<n;i++){
        for (int j=i+1;j<n;j++){
            ll x1=v[i].first, y1 = v[i].second, x2 = v[j].first, y2 = v[j].second;
            double dist = (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
            adj[i].push_back({j,dist});
            adj[j].push_back({i,dist});
        }
    }

    ll visited[n+5];
    memset(visited,-1,sizeof(visited));

    ll l=0,r=2000000000000000000;
    while (l<r){
        ll m = l+(r-l)/2;
        visited[0] = m;
        queue<ll> q;
        q.push(0);
        ll count=0;
        while (!q.empty()){
            ll x = q.front();
            q.pop();
            count++;
            for (auto it=adj[x].begin(); it != adj[x].end(); ++it){
                if (visited[(*it).first]==m) continue;
                if ((*it).second > m) continue;
                visited[(*it).first] = m;
                q.push((*it).first);
            }
        }
        if (count < n) l=m+1;
        else r=m;

    }

    cout << fixed << setprecision(7) << sqrt(l/4);
}

• Subtask 1: 35 / 70