Submission #1254260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254260		MisterReaper	Park (BOI16_park)	C++20	0 / 100	597 ms	25732 KiB

park

// File A.cpp created on 06.08.2025 at 21:20:53
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

struct DSU {
    std::vector<int> f, siz;
    DSU(int n) : f(n), siz(n, 1) {
        std::iota(f.begin(), f.end(), 0);
    }
    int get(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    bool unite(int a, int b) {
        a = get(a), b = get(b);
        if (a == b) {
            return false; 
        } else if (siz[a] > siz[b]) {
            std::swap(a, b);
        }
        f[a] = b;
        siz[b] += siz[a];
        return true;
    }
    bool same(int a, int b) {
        return get(a) == get(b);
    }
    int size(int x) {
        return siz[get(x)];
    }
}; 

int N, M;
int W, H;

i64 sq(int x) {
    return 1LL * x * x;
}

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

    std::cin >> N >> M;
    std::cin >> W >> H;

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

    std::map<std::pair<int, int>, int> points;
    auto insert = [&](int x, int y, int id) -> void {
        if (points.count({x, y}) == 0) {
            points[{x, y}] = id;
        } else {
            assert((points[{x, y}] == id));
        }
    };
    
    std::vector<std::array<int, 3>> edges;
    auto add_edge = [&](int x1, int y1, int x2, int y2, int r1, int r2) {
        int d = std::sqrt(sq(x1 - x2) + sq(y1 - y2));
        if (sq(d) != sq(x1 - x2) + sq(y1 - y2)) {
            d++;
        }
        d -= r1 + r2;
        assert(points.count({x1, y1}));
        assert(points.count({x2, y2}));
        edges.push_back({d, points[{x1, y1}], points[{x2, y2}]});
    };

    for (int i = 0; i < N; ++i) {
        insert(A[i][0], A[i][1], i + 4);
        insert(A[i][0], 0, 0);
        insert(A[i][0], H, 1);
        insert(0, A[i][1], 2);
        insert(W, A[i][1], 3);
        add_edge(A[i][0], A[i][1], 0, A[i][1], A[i][2], 0);
        add_edge(A[i][0], A[i][1], W, A[i][1], A[i][2], 0);
        add_edge(A[i][0], A[i][1], A[i][0], 0, A[i][2], 0);
        add_edge(A[i][0], A[i][1], A[i][0], H, A[i][2], 0);
    }

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < i; ++j) {
            add_edge(A[i][0], A[i][1], A[j][0], A[j][1], A[i][2], A[j][2]);
        }
    }

    std::vector<std::array<int, 3>> qq(M);
    std::vector<std::string> ans(M);
    for (int i = 0; i < M; ++i) {
        int R, E;
        std::cin >> R >> E;
        --E;
        qq[i] = {2 * R, E, i};
    }

    std::sort(qq.begin(), qq.end());
    std::sort(edges.begin(), edges.end());

    int p = 0; 
    DSU dsu(N + 4);
    for (auto[r, e, i] : qq) {
        while (p < edges.size() && edges[p][0] <= r) {
            dsu.unite(edges[p][1], edges[p][2]);
            debug(edges[p]);
            p++;
        }
        debug(r, e, i);
        bool hei = dsu.same(0, 1);
        bool wei = dsu.same(2, 3);
        debug(hei, wei);
        for (int j = 0; j < 4; ++j) {
            if (e == j) {
                ans[i] += char('1' + j);
            } else if ((e == 0 && dsu.same(0, 2))
             || (e == 1 && dsu.same(0, 3))
             || (e == 2 && dsu.same(1, 3))
             || (e == 3 && dsu.same(1, 2))) {
                // bad
            } else if (std::abs(e - j) == 2) {
                if (!hei && !wei) {
                    ans[i] += char('1' + j);
                }
            } else if (e + j == 3) {
                if (!wei) {
                    ans[i] += char('1' + j);
                }
            } else {
                if (!hei) {
                    ans[i] += char('1' + j);
                }
            }
        }
    }

    for (int i = 0; i < M; ++i) {
        std::cout << ans[i] << '\n';
    }

    return 0;
}

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