oj.uz

Submission #374282

# Submission time Handle Problem Language Result Execution time Memory
374282 2021-03-07T06:46:33 Z NONAME Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 244 ms 552 KB 
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int man = 1000;

int n;
int pr[man];
long long a[man], b[man];

long long sq(long long x) {
    return x * x;
}

long long rast(int i, int j) {
    return sq(a[i] - a[j]) + sq(b[i] - b[j]);
}

int f(int x) {
    return (x == pr[x]) ? x : pr[x] = f(pr[x]);
}

void un(int x, int y) {
    x = f(x);
    y = f(y);
    pr[y] = x;
}

bool can(long long x) {
    for (int i = 0; i < n; ++i) {
        pr[i] = i;
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (x >= rast(i, j)) {
                un(i, j);
            }
        }
    }

    set <int> s;
    for (int i = 0; i < n; ++i) {
        s.insert(f(i));
    }
    return (int)(s.size()) == 1;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
    }

    long long l = 0, r = 2e18;
    while (l < r) {
        long long md = (l + r) >> 1LL;
        if (can(md) == true) {
            r = md;
        } else {
            l = md + 1;
        }
    }

    long long ans = (sqrt(l) / (long double)(2)) * 1e7;

    string t = to_string(ans);

    while ((int)(t.size()) < 8) {
        t = "0" + t;
    }
    for (int i = 0; i < (int)(t.size()); ++i) {
        if ((i + 7) == (int)(t.size())) {
            cout << '.';
        }
        cout << t[i];
    }
    cout << "\n";

    return 0;
}

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 2 ms 364 KB Output is correct
4 Correct 3 ms 364 KB Output is correct
5 Correct 3 ms 364 KB Output is correct
6 Correct 108 ms 364 KB Output is correct
7 Correct 107 ms 552 KB Output is correct
8 Correct 233 ms 364 KB Output is correct
9 Correct 244 ms 436 KB Output is correct
10 Correct 124 ms 364 KB Output is correct