Submission #1139850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139850		raphaelp	Park (BOI16_park)	C++20	0 / 100	585 ms	110416 KiB

park

#include <bits/stdc++.h>
using namespace std;
struct Tree
{
    int x, y, r;
};
istream &operator>>(istream &io, Tree &t)
{
    io >> t.x >> t.y >> t.r;
    return io;
}

class UnionFind
{
private:
    vector<int> p;
    int find(int x) { return (p[x] == x) ? x : p[x] = find(p[x]); }

public:
    UnionFind(int x)
    {
        p.assign(x + 4, 0);
        for (int i = 0; i < x + 4; i++)
            p[i] = i;
    }
    void merge(int a, int b)
    {
        int x = find(a), y = find(b);
        if (x == y)
            return;
        p[x] = y;
    }
    int same(int a, int b) { return find(a) == find(b); }
};

int dist(int x1, int y1, int x2, int y2)
{
    long long tot = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
    return floor(sqrt(tot));
}
int main()
{
    int N, M, W, H;
    cin >> N >> M >> W >> H;
    vector<Tree> Trees(N);
    for (int i = 0; i < N; i++)
    {
        cin >> Trees[i];
    }
    vector<vector<int>> collisions;
    for (int i = 0; i < N; i++)
    {
        collisions.push_back({Trees[i].x - Trees[i].r, i, N});
        collisions.push_back({W - Trees[i].x - Trees[i].r, i, N + 2});
        collisions.push_back({Trees[i].y - Trees[i].r, i, N + 1});
        collisions.push_back({H - Trees[i].y - Trees[i].r, i, N + 3});
        for (int j = i + 1; j < N; j++)
        {
            collisions.push_back({dist(Trees[i].x, Trees[i].y, Trees[j].x, Trees[j].y) - Trees[i].r - Trees[j].r, i, j});
        }
    }
    sort(collisions.begin(), collisions.end());
    vector<int> ans(M);
    vector<vector<int>> Tab;
    for (int i = 0; i < M; i++)
    {
        int r, e;
        cin >> r >> e;
        Tab.push_back({r, e - 1, i});
    }
    vector<vector<int>> current(4, vector<int>(4, 1));
    UnionFind UF(N);
    sort(Tab.begin(), Tab.end());
    int buff = 0;
    for (int i = 0; i < M; i++)
    {
        while (buff < collisions.size() && collisions[buff][0] < Tab[i][0] * 2)
        {
            UF.merge(collisions[buff][1], collisions[buff][2]);
            buff++;
        }
        for (int j = 0; j < 4; j++)
        {
            if (UF.same(N + j, N + ((j + 1) % 4)))
            {
                current[j] = {0, 0, 0, 0};
                current[j][j] = 1;
            }
        }
        if (UF.same(N, N + 2))
        {
            current[0][2] = current[0][3] = current[1][2] = current[1][3] = 0;
        }
        if (UF.same(N + 1, N + 3))
            current[0][1] = current[0][2] = current[3][1] = current[3][2] = 0;
        for (int j = 0; j < 4; j++)
        {
            if (current[Tab[i][1]][j] && current[j][Tab[i][1]])
            {
                ans[Tab[i][2]] *= 10;
                ans[Tab[i][2]] += j + 1;
            }
        }
    }
    for (auto val : ans)
        cout << val << '\n';
}

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