oj.uz

답안 #513035

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
513035 2022-01-17T01:23:22 Z KoD Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 113 ms 8184 KB 
#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using i64 = std::int64_t;

struct SimpleQueue {
    int idx;
    vector<int> data;
    SimpleQueue(const int n) : idx(0) { data.reserve(n); }
    void clear() {
        idx = 0;
        data.clear();
    }
    void push(const int x) {
        data.push_back(x);
    }
    int pop() {
        return data[idx++];
    }
    bool empty() const {
        return idx == (int)data.size();
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    vector<double> X(N), Y(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> X[i] >> Y[i];
    }
    vector dis(N, vector<double>(N));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            dis[i][j] = std::hypot(X[i] - X[j], Y[i]- Y[j]);
        }
    }
    vector<char> reach(N);
    SimpleQueue que(N);
    const auto check = [&](const double thres) {
        std::fill(reach.begin(), reach.end(), false);
        que.clear();
        const auto push = [&](const int u) {
            if (!reach[u]) {
                reach[u] = true;
                que.push(u);
            }
        };
        push(0);
        while (!que.empty()) {
            const int u = que.pop();
            for (int v = 0; v < N; ++v) {
                if (dis[u][v] <= 2.0 * thres) {
                    push(v);
                }
            }
        }
        return std::count(reach.begin(), reach.end(), true) == N;
    };
    double ok = 2.0 * 1e9, ng = 0.0;
    for (int step = 0; step < 55; ++step) {
        const double md = (ok + ng) / 2.0;
        (check(md) ? ok : ng) = md;
    }
    std::cout << std::fixed << std::setprecision(20);
    std::cout << ok << '\n';
    return 0;
}

Subtask #1
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 28 ms 2252 KB Output is correct
7 Correct 30 ms 2252 KB Output is correct
8 Correct 57 ms 4684 KB Output is correct
9 Correct 105 ms 8160 KB Output is correct
10 Correct 113 ms 8184 KB Output is correct