Submission #670041

#	Time	Username	Problem	Language	Result	Execution time	Memory
670041		finn__	Park (BOI16_park)	C++17	100 / 100	373 ms	56700 KiB

park

#include <bits/stdc++.h>
using namespace std;

#define sq(x) ((x) * (x))
#define dis(x1, y1, x2, y2, r1, r2) (sqrt(sq(x1 - x2) + sq(y1 - y2)) - r1 - r2)

struct dsu
{
    vector<int> z;

    dsu(size_t n)
    {
        z = vector<int>(n, -1);
    }

    int repr(int u)
    {
        return z[u] < 0 ? u : (z[u] = repr(z[u]));
    }

    void unite(int u, int v)
    {
        u = repr(u);
        v = repr(v);

        if (u == v)
            return;

        if (z[u] < z[v])
            swap(u, v);
        z[v] += z[u];
        z[u] = v;
    }

    bool connected(int u, int v)
    {
        return repr(u) == repr(v);
    }
};

struct tree
{
    int64_t x, y, r;
};

struct event
{
    size_t i, j;
    double t;

    bool operator<(event const &e) const
    {
        return t < e.t;
    }
};

struct visitor
{
    int64_t r, e;
    size_t i;

    bool operator<(visitor const &v) const
    {
        return r < v.r;
    }
};

int main()
{
    size_t n, m, w, h;
    cin >> n >> m >> w >> h;

    vector<tree> trees(n);
    for (auto &[x, y, r] : trees)
        cin >> x >> y >> r;
    vector<visitor> visitors(m);
    for (size_t i = 0; i < m; i++)
    {
        cin >> visitors[i].r >> visitors[i].e;
        visitors[i].i = i;
    }

    vector<event> events;
    for (size_t i = 0; i < n; i++)
    {
        auto const &[x1, y1, r1] = trees[i];
        for (size_t j = i + 1; j < n; j++)
        {
            auto const &[x2, y2, r2] = trees[j];
            events.push_back({i, j, dis(x1, y1, x2, y2, r1, r2)});
        }

        events.push_back({i, n, (double)(x1 - r1)});
        events.push_back({i, n + 1, (double)(y1 - r1)});
        events.push_back({i, n + 2, (double)(w - x1 - r1)});
        events.push_back({i, n + 3, (double)(h - y1 - r1)});
    }

    sort(events.begin(), events.end());
    sort(visitors.begin(), visitors.end());

    dsu d(n + 4);
    auto it = events.begin();
    vector<vector<int>> ans(m);

    for (auto const [r, e, i] : visitors)
    {
        while (it != events.end() && it->t + 1e-3 <= 2.0 * (double)r)
        {
            d.unite(it->i, it->j);
            it++;
        }

        ans[i].push_back(e);

        switch (e)
        {
        case 1:
            if (!d.connected(n, n + 1))
            {
                if (!d.connected(n + 1, n + 3) && !d.connected(n + 1, n + 2))
                    ans[i].push_back(2);
                if (!d.connected(n, n + 2) && !d.connected(n + 1, n + 3) && !d.connected(n + 2, n + 3))
                    ans[i].push_back(3);
                if (!d.connected(n, n + 2) && !d.connected(n, n + 3))
                    ans[i].push_back(4);
            }
            break;
        case 2:
            if (!d.connected(n + 1, n + 2))
            {
                if (!d.connected(n, n + 2) && !d.connected(n + 2, n + 3))
                    ans[i].push_back(3);
                if (!d.connected(n, n + 2) && !d.connected(n + 1, n + 3) && !d.connected(n, n + 3))
                    ans[i].push_back(4);
                if (!d.connected(n + 1, n + 3) && !d.connected(n, n + 1))
                    ans[i].push_back(1);
            }
            break;
        case 3:
            if (!d.connected(n + 2, n + 3))
            {
                if (!d.connected(n + 1, n + 3) && !d.connected(n, n + 3))
                    ans[i].push_back(4);
                if (!d.connected(n, n + 2) && !d.connected(n + 1, n + 3) && !d.connected(n, n + 1))
                    ans[i].push_back(1);
                if (!d.connected(n, n + 2) && !d.connected(n + 1, n + 2))
                    ans[i].push_back(2);
            }
            break;
        case 4:
            if (!d.connected(n, n + 3))
            {
                if (!d.connected(n, n + 2) && !d.connected(n, n + 1))
                    ans[i].push_back(1);
                if (!d.connected(n, n + 2) && !d.connected(n + 1, n + 3) && !d.connected(n + 1, n + 2))
                    ans[i].push_back(2);
                if (!d.connected(n + 1, n + 3) && !d.connected(n + 2, n + 3))
                    ans[i].push_back(3);
            }
            break;
        }

        sort(ans[i].begin(), ans[i].end());
    }

    for (auto const &v : ans)
    {
        for (auto const x : v)
            cout << x;
        cout << '\n';
    }
}

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