제출 #529418

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
529418		KoD	Park (BOI16_park)	C++17	27 / 100	2563 ms	1372 KiB

park

#include <bits/stdc++.h>

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

using ll = long long;

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;
    }
};

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;
    ll W, H;
    std::cin >> W >> H;
    vector<ll> 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 int bottom = N, top = N + 1, left = N + 2, right = N + 3;

    const auto set_radius = [&](const ll rad) {
        dsu.reset();
        for (int i = 0; i < N; ++i) {
            if (Y[i] < R[i] + 2 * rad) {
                dsu.merge(i, bottom);
            }
            if (H - Y[i] < R[i] + 2 * rad) {
                dsu.merge(i, top);
            }
            if (X[i] < R[i] + 2 * rad) {
                dsu.merge(i, left);
            }
            if (W - X[i] < R[i] + 2 * rad) {
                dsu.merge(i, right);
            }
        }
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < i; ++j) {
                const ll dx = X[i] - X[j];
                const ll dy = Y[i] - Y[j];
                if (sq(dx) + sq(dy) < sq(R[i] + R[j] + 2 * rad)) {
                    dsu.merge(i, j);
                }
            }
        }
    };

    const auto check = [&](int x, int y) {
        if (x == y) return true;
        if (x > y) std::swap(x, y);
        const int b = dsu.find(bottom), t = dsu.find(top), l = dsu.find(left), r = dsu.find(right);
        if (x == 1 and y == 2) return b != t and b != l and b != r;
        if (x == 1 and y == 3) return b != t and b != l and l != r and t != r;
        if (x == 1 and y == 4) return l != b and l != r and l != t;
        if (x == 2 and y == 3) return r != b and r != l and r != t;
        if (x == 2 and y == 4) return b != r and b != t and l != t and l != r;
        if (x == 3 and y == 4) return t != b and t != l and t != r;
        return false;
    };

    while (M--) {
        int rad, enter;
        std::cin >> rad >> enter;
        set_radius(rad);
        for (int i = 1; i <= 4; ++i) {
            if (check(enter, i)) {
                std::cout << i;
            }
        }
        std::cout << '\n';
    }

    return 0;
}

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