Submission #1320025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320025		camil7	Odašiljači (COCI20_odasiljaci)	C++20	56 / 70	127 ms	9072 KiB

odasiljaci

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define ll long long
#define ull unsigned long long
#define lb lower_bound
#define ub upper_bound
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

void solve() {
    int n;
    cin >> n;
    vector<pair<int, int>> vt;
    for (int i = 1; i <= n; i++){
        int a, b;
        cin >> a >> b;
        vt.push_back({a, b});
    }
    double l = 0.0, r = 1e6, best = 0.0;
    for(int times = 1; times <= 100; times++){
        double m = (l + r) / 2 * 1.0;
        vector<int> adj[n + 5];
        for (int i = 1; i <= n; i++){
            for (int j = i + 1; j <= n; j++){
                pair<int, int> p1 = vt[i - 1], p2 =  vt[j - 1];
                if(sqrt(abs(p1.first - p2.first)*abs(p1.first - p2.first) + abs(p1.second - p2.second)*abs(p1.second - p2.second)) / 2 <= m){
                    adj[i].push_back(j);
                    adj[j].push_back(i);
                }
            }
        }
        int dis[n + 5];
        memset(dis, -1, sizeof(dis));
        queue<int> q;
        q.push(1);
        dis[1] = 0;
        while(q.size()){
            int x = q.front();
            q.pop();
            for(int i : adj[x]){
                if(dis[i] == -1){
                    q.push(i);
                    dis[i] = dis[x] + 1;
                }
            }
        }
        bool ok = true;
        for (int i = 1; i <= n; i++)if(dis[i] == -1)ok = false;
        if(ok){
            r = m;
            best = m;
        }
        else l = m;
    }
    cout << setprecision(10) << fixed << best << endl;
}
signed main() {
    IOS;
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}

• Subtask 1: 56 / 70