oj.uz

Submission #1067188

# Submission time Handle Problem Language Result Execution time Memory
1067188 2024-08-20T12:37:42 Z 12345678 Park (BOI16_park) C++17
100 / 100
 514 ms 62552 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5;

ll n, q, h, w, x[nx], y[nx], rad[nx], en[nx], len[nx], dsu[nx], f[5][5];
vector<tuple<ll, ll, ll>> edg;
vector<pair<ll, ll>> qrs;
vector<ll> ans[nx];

ll find(ll x)
{
    if (dsu[x]==x) return x;
    return dsu[x]=find(dsu[x]);
}

ll bsearch(ll x)
{
    ll l=0, r=2e9;
    while (l<r)
    {
        ll md=(l+r+1)/2;
        if (md*md<=x) l=md;
        else r=md-1;
    }
    return l;
}

void fail(vector<ll> a, vector<ll> b)
{
    for (auto x:a) for (auto y:b) f[x][y]=f[y][x]=1;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>q>>w>>h;
    for (int i=1; i<=n; i++) cin>>x[i]>>y[i]>>rad[i];
    for (int i=1; i<=n; i++)
    {
        edg.push_back({x[i]-rad[i], i, n+1});
        edg.push_back({y[i]-rad[i], i, n+2});
        edg.push_back({w-x[i]-rad[i], i, n+3});
        edg.push_back({h-y[i]-rad[i], i, n+4});
    }
    for (int i=1; i<=n; i++)
    {
        for (int j=i+1; j<=n; j++)
        {
            ll dist=bsearch((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))-rad[i]-rad[j];
            edg.push_back({dist, i, j});
        }
    }
    sort(edg.begin(), edg.end());
    reverse(edg.begin(), edg.end());
    for (int i=1; i<=q; i++) cin>>len[i]>>en[i], qrs.push_back({2*len[i], i});
    sort(qrs.begin(), qrs.end());
    for (int i=1; i<=n+4; i++) dsu[i]=i;
    for (int t=0; t<q; t++)
    {
        while (!edg.empty()&&get<0>(edg.back())<qrs[t].first)
        {
            auto [w, u, v]=edg.back();
            //cout<<"merge "<<u<<' '<<v<<'\n';
            edg.pop_back();
            dsu[find(u)]=find(v);
        }
        if (find(n+1)==find(n+2)) fail({1}, {2, 3, 4});
        if (find(n+1)==find(n+3)) fail({1, 2}, {3, 4});
        if (find(n+1)==find(n+4)) fail({4}, {1, 2, 3});
        if (find(n+2)==find(n+3)) fail({2}, {1, 3, 4});
        if (find(n+2)==find(n+4)) fail({1, 4}, {2, 3});
        if (find(n+3)==find(n+4)) fail({3}, {1, 2, 4});
        int idx=qrs[t].second;
        //cout<<"dist "<<idx<<' '<<len[idx]<<'\n';
        for (int i=1; i<=4; i++) if (!f[en[idx]][i]) ans[idx].push_back(i);
    }
    for (int i=1; i<=q; i++)
    {
        for (auto t:ans[i]) cout<<t;
        cout<<'\n';
    }
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 56864 KB Output is correct
2 Correct 466 ms 58020 KB Output is correct
3 Correct 473 ms 56600 KB Output is correct
4 Correct 461 ms 56484 KB Output is correct
5 Correct 472 ms 58036 KB Output is correct
6 Correct 465 ms 56740 KB Output is correct
7 Correct 422 ms 57252 KB Output is correct
8 Correct 415 ms 56424 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 14260 KB Output is correct
2 Correct 48 ms 14020 KB Output is correct
3 Correct 47 ms 13756 KB Output is correct
4 Correct 47 ms 14136 KB Output is correct
5 Correct 47 ms 14012 KB Output is correct
6 Correct 45 ms 14016 KB Output is correct
7 Correct 55 ms 13176 KB Output is correct
8 Correct 44 ms 13284 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 56864 KB Output is correct
2 Correct 466 ms 58020 KB Output is correct
3 Correct 473 ms 56600 KB Output is correct
4 Correct 461 ms 56484 KB Output is correct
5 Correct 472 ms 58036 KB Output is correct
6 Correct 465 ms 56740 KB Output is correct
7 Correct 422 ms 57252 KB Output is correct
8 Correct 415 ms 56424 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct
11 Correct 45 ms 14260 KB Output is correct
12 Correct 48 ms 14020 KB Output is correct
13 Correct 47 ms 13756 KB Output is correct
14 Correct 47 ms 14136 KB Output is correct
15 Correct 47 ms 14012 KB Output is correct
16 Correct 45 ms 14016 KB Output is correct
17 Correct 55 ms 13176 KB Output is correct
18 Correct 44 ms 13284 KB Output is correct
19 Correct 512 ms 62552 KB Output is correct
20 Correct 507 ms 62096 KB Output is correct
21 Correct 513 ms 61604 KB Output is correct
22 Correct 514 ms 61852 KB Output is correct
23 Correct 507 ms 61340 KB Output is correct
24 Correct 461 ms 60828 KB Output is correct