Submission #1067188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067188		12345678	Park (BOI16_park)	C++17	100 / 100	514 ms	62552 KiB

park

#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 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42