Submission #1249164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249164		chikien2009	Park (BOI16_park)	C++20	100 / 100	306 ms	25236 KiB

park

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

struct DSU
{
    int par[20000], sz[20000];
    inline DSU()
    {
        for (int i = 0; i < 2e4; ++i)
        {
            par[i] = i;
            sz[i] = 1;
        }
    }
    inline int Get(int inp)
    {
        return (par[inp] == inp ? inp : par[inp] = Get(par[inp]));
    }
    inline void Combine(int ina, int inb)
    {
        ina = Get(ina);
        inb = Get(inb);
        if (ina != inb)
        {
            if (sz[ina] < sz[inb])
            {
                swap(ina, inb);
            }
            par[inb] = ina;
            sz[ina] += sz[inb];
        }
    }
} dsu;

int n, m, h, w, a[2005], b[2005], c[2005], f[4][4], g[4][4];
vector<array<int, 3>> e;

inline int Dist(long long x, long long y)
{
    return floor(sqrtl(x * x + y * y));
}

int main()
{
    setup();

    cin >> n >> m >> w >> h;
    for (int i = 0; i < 4; ++i)
    {
        fill_n(f[i], 4, 2e9);
        fill_n(g[i], 4, 2e9);
    }
    for (int i = 4; i < n + 4; ++i)
    {
        cin >> a[i] >> b[i] >> c[i];
        for (int j = 4; j < i; ++j)
        {
            e.push_back({Dist(a[i] - a[j], b[i] - b[j]) - c[i] - c[j], i, j});
        }
        e.push_back({a[i] - c[i], 0, i});
        e.push_back({b[i] - c[i], 1, i});
        e.push_back({w - a[i] - c[i], 2, i});
        e.push_back({h - b[i] - c[i], 3, i});
    }
    sort(e.begin(), e.end());
    for (auto &i : e)
    {
        dsu.Combine(i[1], i[2]);
        for (int j = 0; j < 4; ++j)
        {
            for (int k = 0; k < 4; ++k)
            {
                if (dsu.Get(j) == dsu.Get(k))
                {
                    f[j][k] = min(f[j][k], i[0]);
                }
            }
        }
    }
    g[0][1] = g[1][0] = min({f[1][3], f[1][0], f[1][2]});
    g[2][3] = g[3][2] = min({f[3][0], f[3][1], f[3][2]});
    g[0][3] = g[3][0] = min({f[0][1], f[0][2], f[0][3]});
    g[1][2] = g[2][1] = min({f[2][1], f[2][0], f[2][3]});
    g[0][2] = g[2][0] = min({f[1][3], f[0][2], f[0][1], f[2][3]});
    g[1][3] = g[3][1] = min({f[1][2], f[0][3], f[1][3], f[0][2]});
    while (m--)
    {
        cin >> w >> h;
        h--;
        for (int i = 0; i < 4; ++i)
        {
            if (2 * w <= g[h][i])
            {
                cout << i + 1;
            }
        }
        cout << "\n";
    }
    return 0;
}

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