Submission #1250598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250598		minhpk	Park (BOI16_park)	C++20	100 / 100	273 ms	81632 KiB

park

#include <bits/stdc++.h>
#define int long long 
using namespace std;
int a, b;
int w, h;

double cal(int x, int y, int u, int v)
{
    return sqrt((x - u) * (x - u) + (y - v) * (y - v));
}

struct edge
{
    int x, y;
    double val;
};

vector<edge> v;
edge z[1000005];

int par[1000005];
int sz[1000005];

int find(int u)
{
    return par[u] == u ? u : par[u] = find(par[u]);
}

void join(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y)
        return;
    if (sz[x] < sz[y])
        swap(x, y);
    par[y] = x;
    sz[x] += sz[y];
}

struct query
{
    int r, sta, id;
};
query qarr[1000005];
string res[1000005];

bool linked(int u, int v)
{
    return find(u) == find(v);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> a >> b;
    cin >> w >> h;

    for (int i = 1; i <= a; ++i)
    {
        int x, y, r;
        cin >> x >> y >> r;
        z[i] = {x, y, (double)r};
        v.push_back({i, a + 1,( y - r)*1.0});
        v.push_back({i, a + 2, ((h - y) - r)*1.0});
        v.push_back({i, a + 3, (x - r)*1.0});
        v.push_back({i, a + 4, ((w - x) - r)*1.0});
        for (int j = 1; j < i; ++j)
        {
            double d = cal(x, y, z[j].x, z[j].y) - r - z[j].val;
            v.push_back({i, j, d});
        }
    }
    sort(v.begin(), v.end(), [](auto &a, auto &b)
         { return a.val < b.val; });

    
    for (int i = 1; i <= b; ++i)
    {
        cin >> qarr[i].r >> qarr[i].sta;
        qarr[i].id = i;
    }
    sort(qarr + 1, qarr + 1 + b, [](auto &a, auto &b)
         { return a.r < b.r; });

    for (int i = 1; i <= a + 4; ++i)
    {
        par[i] = i;
        sz[i] = 1;
    }
    int ptr = 0;
    for (int i = 1; i <= b; ++i)
    {
        int r = qarr[i].r;
        int sta = qarr[i].sta;
        int id = qarr[i].id;
        while (ptr < (int)v.size() && v[ptr].val < 2.0 * r)
        {
            join(v[ptr].x, v[ptr].y);
            ++ptr;
        }
        int B1 = a + 1, B2 = a + 2, B3 = a + 3, B4 = a + 4;
        string s;
        if (sta == 1)
        {
            if (linked(B1, B3))
                s += '1';
            else
            {
                s += '1';
                if (!linked(B1, B2) && !linked(B4, B1))
                    s += '2';
                if (!linked(B3, B4) && !linked(B2, B4) && !linked(B1, B2))
                    s += '3';
                if (!linked(B3, B4) && !linked(B2, B3))
                    s += '4';
            }
        }
        else if (sta == 2)
        {
            if (linked(B1, B4))
                s += '2';
            else
            {
                if (!linked(B1, B2) && !linked(B3, B1))
                    s += '1';
                s += '2';
                if (!linked(B3, B4) && !linked(B2, B4))
                    s += '3';
                if (!linked(B3, B4) && !linked(B2, B3) && !linked(B1, B2))
                    s += '4';
            }
        }
        else if (sta == 3)
        {
            if (linked(B2, B4))
                s += '3';
            else
            {
                if (!linked(B3, B4) && !linked(B1, B3) && !linked(B1, B2))
                    s += '1';
                if (!linked(B3, B4) && !linked(B4, B1))
                    s += '2';
                s += '3';
                if (!linked(B1, B2) && !linked(B2, B3))
                    s += '4';
            }
        }
        else if (sta == 4)
        {
            if (linked(B2, B3))
                s += '4';
            else
            {
                if (!linked(B3, B4) && !linked(B3, B1))
                    s += '1';
                if (!linked(B3, B4) && !linked(B1, B4) && !linked(B1, B2))
                    s += '2';
                if (!linked(B1, B2) && !linked(B2, B4))
                    s += '3';
                s += '4';
            }
        }
        res[id] = s;
    }

    for (int i = 1; i <= b; ++i)
        cout << res[i] << '\n';
    return 0;

}

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