Submission #481796

#	Time	Username	Problem	Language	Result	Execution time	Memory
481796		Rainbowbunny	Park (BOI16_park)	C++17	100 / 100	275 ms	33480 KiB

park

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 3055;
const long long INF = 1e18;
 
int n, q;
int h, w;
int dsu[MAXN], rnk[MAXN];
long long Con[4][4];
long long x[MAXN], y[MAXN], r[MAXN];
vector <tuple <long long, int, int> > Edges;
 
long long dist(long long x, long long y, long long z, long long t)
{
    long long d = (x - z) * (x - z) + (y - t) * (y - t);
    return (long long)sqrt(d);
}
 
int Root(int node)
{
    return dsu[node] == node ? node : dsu[node] = Root(dsu[node]);
}
 
void Union(int x, int y)
{
    if((x = Root(x)) == (y = Root(y)))
    {
        return;
    }
    if(rnk[x] > rnk[y])
    {
        swap(x, y);
    }
    dsu[y] = x;
    if(rnk[y] == rnk[x])
    {
        rnk[x]++;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for(int i = 0; i < 4; i++)
    {
        for(int j = 0; j < 4; j++)
        {
            Con[i][j] = INF;
        }
    }
    cin >> n >> q >> w >> h;
    for(int i = 0; i <= n + 3; i++)
    {
        dsu[i] = i;
    }
    for(int i = 4; i <= n + 3; i++)
    {
        cin >> x[i] >> y[i] >> r[i];
        for(int j = 4; j < i; j++)
        {
            Edges.emplace_back(dist(x[i], y[i], x[j], y[j]) - r[i] - r[j], i, j);
        }
        Edges.emplace_back(x[i] - r[i], 0, i);
        Edges.emplace_back(y[i] - r[i], 1, i);
        Edges.emplace_back(w - x[i] - r[i], 2, i);
        Edges.emplace_back(h - y[i] - r[i], 3, i);
    }
    sort(Edges.begin(), Edges.end());
    for(auto x : Edges)
    {
        int u, v;
        long long c;
        tie(c, u, v) = x;
        Union(u, v);
        for(int i = 0; i < 4; i++)
        {
            for(int j = i + 1; j < 4; j++)
            {
                if(Con[i][j] == INF and Root(i) == Root(j))
                {
                    Con[i][j] = c;
                }
            }
        } 
    }
    while(q--)
    {
        int e;
        long long r;
        string ans;
        cin >> r >> e;
        r *= 2;
        if(e == 1)
        {
            ans.push_back('1');
            if(r <= min({Con[0][1], Con[1][3], Con[1][2]}))
            {
                ans.push_back('2');
            }
            if(r <= min({Con[0][1], Con[1][3], Con[2][3], Con[0][2]}))
            {
                ans.push_back('3');
            }
            if(r <= min({Con[0][1], Con[0][2], Con[0][3]}))
            {
                ans.push_back('4');
            }
        }
        else if(e == 2)
        {
            if(r <= min({Con[0][1], Con[1][3], Con[1][2]}))
            {
                ans.push_back('1');
            }
            ans.push_back('2');
            if(r <= min({Con[0][2], Con[1][2], Con[2][3]}))
            {
                ans.push_back('3');
            }
            if(r <= min({Con[0][3], Con[1][2], Con[0][2], Con[1][3]}))
            {
                ans.push_back('4');
            }
        }
        else if(e == 3)
        {
            if(r <= min({Con[0][1], Con[1][3], Con[0][2], Con[2][3]}))
            {
                ans.push_back('1');
            }
            if(r <= min({Con[0][2], Con[1][2], Con[2][3]}))
            {
                ans.push_back('2');
            }
            ans.push_back('3');
            if(r <= min({Con[0][3], Con[1][3], Con[2][3]}))
            {
                ans.push_back('4');
            }
        }
        else
        {
            if(r <= min({Con[0][1], Con[0][2], Con[0][3]}))
            {
                ans.push_back('1');
            }
            if(r <= min({Con[0][3], Con[1][3], Con[0][2], Con[1][2]}))
            {
                ans.push_back('2');
            }
            if(r <= min({Con[0][3], Con[1][3], Con[2][3]}))
            {
                ans.push_back('3');
            }
            ans.push_back('4');
        }
        cout << ans << '\n';
    }
}

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