Submission #1101783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101783		KLKLK	Park (BOI16_park)	C++17	100 / 100	440 ms	72900 KiB

park

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <tuple>
#include <cmath>
#include <cstdint>

#define LL long long
#define LD long double
#define CYL tuple<int, int, int>
#define EDG tuple<LD, int, int>
#define QRY tuple<int, int, int>

using namespace std;

class DisjointSetUnion
{
    int n;
    vector<int> root;
    vector<int> size;

    int find(int v)
    {
        if (root[v] != v) root[v] = find(root[v]);
        return root[v];
    }

public:
    explicit DisjointSetUnion(int n) : n(n), root(vector<int>(n)), size(vector<int>(n, 1))
    {
        for (int i = 0; i < n; ++i) root[i] = i;
    }

    bool query(int a, int b)
    {
        a = find(a);
        b = find(b);
        return a == b;
    }

    void join(int a, int b)
    {
        a = find(a);
        b = find(b);
        if (a == b) return;

        if (size[a] < size[b]) swap(a, b);
        size[a] += size[b];
        root[b] = a;
    }
};

LD distance(LD x1, LD x2, LD y1, LD y2)
{
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

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

    int n, q, w, h;
    cin >> n >> q >> w >> h;

    vector<CYL> cylinder(n);
    vector<QRY> queries(q);
    vector<string> ans(q);
    vector<EDG> edges;

    LL x, y, r;
    for (int i = 0; i < n; ++i)
    {
        cin >> x >> y >> r;
        cylinder[i] = {x, y, r};
        edges.emplace_back(x - r, i, n);
        edges.emplace_back(y - r, i, n + 1);
        edges.emplace_back(w - x - r, i, n + 2);
        edges.emplace_back(h - y - r, i, n + 3);
    }

    for (int i = 0; i < n; ++i)
    {
        auto [x1, y1, r1] = cylinder[i];
        for (int j = i + 1; j < n; ++j)
        {
            auto [x2, y2, r2] = cylinder[j];
            edges.emplace_back(distance(x1, x2, y1, y2) - r1 - r2, i, j);
        }
    }
    sort(edges.begin(), edges.end());

    int c;
    for (int i = 0; i < q; ++i)
    {
        cin >> r >> c;
        queries[i] = {r, c - 1, i};
    }
    sort(queries.begin(), queries.end());

    DisjointSetUnion U = DisjointSetUnion(n + 4);
    auto edg_itr = edges.begin();
    for (int i = 0; i < q; ++i)
    {
        auto [radius, hole, idx] = queries[i];
        for (; edg_itr != edges.end(); ++edg_itr)
        {
            auto [dist, a, b] = *edg_itr;
            if (dist >= 2 * radius) break;
            U.join(a, b);
        }

        bool blocked = U.query(n + hole, n + (hole + 1) % 4);
        if (blocked)
        {
            ans[idx] += '1' + hole;
            continue;
        }
        bool horizontal = U.query(n, n + 2);
        bool vertical = U.query(n + 1, n + 3);

        for (int h = 0; h < 4; ++h)
        {
            if (h == hole)
            {
                ans[idx] += '1' + h;
                continue;
            }
            if (U.query(n + h, n + (h + 1) % 4)) continue;
            if ((__builtin_popcount(h) % 2) != (__builtin_popcount(hole) % 2) && vertical) continue;
            if ((h / 2) != (hole / 2) && horizontal) continue;
            ans[idx] += '1' + h;
        }
    }

    for (int i = 0; i < q; ++i) cout << ans[i] << "\n";
}

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