oj.uz

Submission #1101783

# Submission time Handle Problem Language Result Execution time Memory
1101783 2024-10-16T18:51:47 Z KLKLK Park (BOI16_park) C++17
100 / 100
 440 ms 72900 KB 
#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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 68300 KB Output is correct
2 Correct 399 ms 68300 KB Output is correct
3 Correct 393 ms 68284 KB Output is correct
4 Correct 391 ms 68288 KB Output is correct
5 Correct 422 ms 68272 KB Output is correct
6 Correct 388 ms 68288 KB Output is correct
7 Correct 359 ms 68268 KB Output is correct
8 Correct 357 ms 68276 KB Output is correct
9 Correct 1 ms 352 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 6848 KB Output is correct
2 Correct 34 ms 6820 KB Output is correct
3 Correct 33 ms 6860 KB Output is correct
4 Correct 36 ms 6864 KB Output is correct
5 Correct 36 ms 6876 KB Output is correct
6 Correct 34 ms 6852 KB Output is correct
7 Correct 28 ms 6220 KB Output is correct
8 Correct 37 ms 6220 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 68300 KB Output is correct
2 Correct 399 ms 68300 KB Output is correct
3 Correct 393 ms 68284 KB Output is correct
4 Correct 391 ms 68288 KB Output is correct
5 Correct 422 ms 68272 KB Output is correct
6 Correct 388 ms 68288 KB Output is correct
7 Correct 359 ms 68268 KB Output is correct
8 Correct 357 ms 68276 KB Output is correct
9 Correct 1 ms 352 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 33 ms 6848 KB Output is correct
12 Correct 34 ms 6820 KB Output is correct
13 Correct 33 ms 6860 KB Output is correct
14 Correct 36 ms 6864 KB Output is correct
15 Correct 36 ms 6876 KB Output is correct
16 Correct 34 ms 6852 KB Output is correct
17 Correct 28 ms 6220 KB Output is correct
18 Correct 37 ms 6220 KB Output is correct
19 Correct 440 ms 72876 KB Output is correct
20 Correct 420 ms 72892 KB Output is correct
21 Correct 434 ms 72796 KB Output is correct
22 Correct 411 ms 72892 KB Output is correct
23 Correct 421 ms 72812 KB Output is correct
24 Correct 389 ms 72900 KB Output is correct