Submission #739667

#	Time	Username	Problem	Language	Result	Execution time	Memory
739667		n0sk1ll	Park (BOI16_park)	C++17	100 / 100	870 ms	70464 KiB

park

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

const int N=2023;
int up[N+3];

int Up(int x)
{
    if (up[x]<0) return x;
    return up[x]=Up(up[x]);
}

void dsu(int a, int b)
{
    a=Up(a),b=Up(b);
    if (a==b) return;
    if (up[a]<up[b]) swap(a,b);
    up[b]+=up[a],up[a]=b;
}

bool spojeni(int a, int b)
{
    return Up(a)==Up(b);
}

int x[N+3],y[N+3],r[N+3];

ld dist(int a, int b, int c, int d)
{
    return sqrt((ld)(c-a)*(c-a)+(ld)(d-b)*(d-b));
}

string ans[100005];

bool unutar(int a, int b, int c)
{
    return a<c && c<=b;
}

int main()
{
    FAST;

    int n,m; cin>>n>>m;
    int w,h; cin>>w>>h;
    ff(i,0,n) cin>>x[i]>>y[i]>>r[i];

    vector<pair<ld,pii>> dists;
    ff(i,0,n) ff(j,i+1,n) dists.pb({dist(x[i],y[i],x[j],y[j])-r[i]-r[j],{i,j}});
    ff(i,0,n)
    {
        dists.pb({y[i]-r[i],{i,n}});
        dists.pb({w-x[i]-r[i],{i,n+1}});
        dists.pb({h-y[i]-r[i],{i,n+2}});
        dists.pb({x[i]-r[i],{i,n+3}});
    }
    sort(all(dists),greater<pair<int,pii>>());

    vector<pair<pii,int>> ljudi;
    ff(i,0,m)
    {
        int tr,ty;
        cin>>tr>>ty;
        ljudi.pb({{tr,ty},i});
    }
    sort(all(ljudi));

    ff(i,0,n+4) up[i]=-1;
    //n   - dole
    //n+1 - desno
    //n+2 - gore
    //n+3 - levo

    for (auto lj : ljudi)
    {
        int tr=lj.xx.xx,ty=lj.xx.yy,ind=lj.yy;
        while (!dists.empty() && dists.back().xx<2*tr)
        {
            //cout<<"spajam "<<dists.back().yy.xx<<" i "<<dists.back().yy.yy<<endl;
            dsu(dists.back().yy.xx,dists.back().yy.yy),dists.popb();
        }

        vector<bool> blok(4,false);

        ff(i,0,4) ff(j,i+1,4) ff(dest,0,4)
        {
            if (unutar(i,j,dest)^unutar(i,j,ty-1))
                if (spojeni(n+i,n+j))
                    blok[dest]=true;
        }

        ff(i,0,4) if (!blok[i]) ans[ind].pb('1'+i);
        //cout<<"answerujem "<<ind<<" sa "<<ans[ind]<<endl;
    }

    ff(i,0,m) cout<<ans[i]<<"\n";
}

//Note to self: Check for overflow

/*

1 4
7 7
4 4 2
1 1
1 2
1 3
1 4

*/

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