Submission #529434

#	Time	Username	Problem	Language	Result	Execution time	Memory
529434		KoD	Park (BOI16_park)	C++17	100 / 100	2391 ms	1764 KiB

park

#include <bits/stdc++.h>

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

struct UnionFind {
    vector<int> par;
    UnionFind(const int n) : par(n, -1) {}
    void reset() {
        std::fill(par.begin(), par.end(), -1);
    }
    int find(const int u) {
        return par[u] < 0 ? u : par[u] = find(par[u]);
    }
    void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (par[x] > par[y]) std::swap(x, y);
        par[x] += par[y];
        par[y] = x;
    }
};

using ll = long long;

constexpr ll sq(const ll x) {
    return x * x;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, M;
    std::cin >> N >> M;
    int W, H;
    std::cin >> W >> H;
    vector<int> X(N), Y(N), R(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> X[i] >> Y[i] >> R[i];
    }

    UnionFind dsu(N + 4);
    const auto set_radius = [&](const int rad) {
        dsu.reset();
        for (int i = 0; i < N; ++i) {
            if (Y[i] < R[i] + 2 * rad) {
                dsu.merge(i, N);
            }
            if (H - Y[i] < R[i] + 2 * rad) {
                dsu.merge(i, N + 1);
            }
            if (X[i] < R[i] + 2 * rad) {
                dsu.merge(i, N + 2);
            }
            if (W - X[i] < R[i] + 2 * rad) {
                dsu.merge(i, N + 3);
            }
        }
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < i; ++j) {
                if (sq(X[i] - X[j]) + sq(Y[i] - Y[j]) < sq(R[i] + R[j] + 2 * rad)) {
                    dsu.merge(i, j);
                }
            }
        }
    };

    array<array<int, 4>, 4> thres = {};
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < i; ++j) {
            int ok = 0, ng = 1000000000;
            while (ng - ok > 1) {
                const int md = (ok + ng) / 2;
                set_radius(md);
                (dsu.find(N + i) != dsu.find(N + j) ? ok : ng) = md;
            }
            thres[i][j] = thres[j][i] = ok;
        }
    }

    array<array<int, 4>, 4> reach = {};
    reach[0][1] = std::min({thres[0][1], thres[0][2], thres[0][3]});    
    reach[0][3] = std::min({thres[2][0], thres[2][1], thres[2][3]});    
    reach[1][2] = std::min({thres[3][0], thres[3][1], thres[3][2]});    
    reach[2][3] = std::min({thres[1][0], thres[1][2], thres[1][3]});    
    reach[0][2] = std::min({thres[0][1], thres[0][2], thres[3][1], thres[3][2]});    
    reach[1][3] = std::min({thres[0][1], thres[0][3], thres[2][1], thres[2][3]});    

    while (M--) {
        int rad, i;
        std::cin >> rad >> i;
        i -= 1;
        for (int j = 0; j < 4; ++j) {
            if (i == j or rad <= reach[std::min(i, j)][std::max(i, j)]) {
                std::cout << j + 1;
            }
        }
        std::cout << '\n';
    }

    return 0;
}

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42