oj.uz

Submission #481796

# Submission time Handle Problem Language Result Execution time Memory
481796 2021-10-21T23:42:37 Z Rainbowbunny Park (BOI16_park) C++17
100 / 100
 275 ms 33480 KB 
#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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 33480 KB Output is correct
2 Correct 252 ms 33352 KB Output is correct
3 Correct 262 ms 33388 KB Output is correct
4 Correct 245 ms 33380 KB Output is correct
5 Correct 267 ms 33384 KB Output is correct
6 Correct 247 ms 33404 KB Output is correct
7 Correct 250 ms 33340 KB Output is correct
8 Correct 243 ms 33348 KB Output is correct
9 Correct 0 ms 336 KB Output is correct
10 Correct 0 ms 336 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2208 KB Output is correct
2 Correct 29 ms 2100 KB Output is correct
3 Correct 23 ms 2104 KB Output is correct
4 Correct 24 ms 2124 KB Output is correct
5 Correct 25 ms 2200 KB Output is correct
6 Correct 24 ms 2140 KB Output is correct
7 Correct 28 ms 1740 KB Output is correct
8 Correct 23 ms 1772 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 33480 KB Output is correct
2 Correct 252 ms 33352 KB Output is correct
3 Correct 262 ms 33388 KB Output is correct
4 Correct 245 ms 33380 KB Output is correct
5 Correct 267 ms 33384 KB Output is correct
6 Correct 247 ms 33404 KB Output is correct
7 Correct 250 ms 33340 KB Output is correct
8 Correct 243 ms 33348 KB Output is correct
9 Correct 0 ms 336 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 35 ms 2208 KB Output is correct
12 Correct 29 ms 2100 KB Output is correct
13 Correct 23 ms 2104 KB Output is correct
14 Correct 24 ms 2124 KB Output is correct
15 Correct 25 ms 2200 KB Output is correct
16 Correct 24 ms 2140 KB Output is correct
17 Correct 28 ms 1740 KB Output is correct
18 Correct 23 ms 1772 KB Output is correct
19 Correct 275 ms 33464 KB Output is correct
20 Correct 263 ms 33440 KB Output is correct
21 Correct 267 ms 33428 KB Output is correct
22 Correct 267 ms 33388 KB Output is correct
23 Correct 261 ms 33456 KB Output is correct
24 Correct 268 ms 33464 KB Output is correct