제출 #1139851

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139851		raphaelp	Park (BOI16_park)	C++20	100 / 100	614 ms	117488 KiB

park

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

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

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

long long dist(long long x1, long long y1, long long x2, long long y2)
{
    long long tot = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
    return floor(sqrt(tot));
}
int main()
{
    long long N, M, W, H;
    cin >> N >> M >> W >> H;
    vector<Tree> Trees(N);
    for (long long i = 0; i < N; i++)
    {
        cin >> Trees[i];
    }
    vector<vector<long long>> collisions;
    for (long long 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 (long long 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<long long> ans(M);
    vector<vector<long long>> Tab;
    for (long long i = 0; i < M; i++)
    {
        long long r, e;
        cin >> r >> e;
        Tab.push_back({r, e - 1, i});
    }
    vector<vector<long long>> current(4, vector<long long>(4, 1));
    UnionFind UF(N);
    sort(Tab.begin(), Tab.end());
    long long buff = 0;
    for (long long 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 (long long 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 (long long 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: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42