Submission #1134205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134205		kitkat12	Park (BOI16_park)	C++20	100 / 100	274 ms	38968 KiB

park

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define debug(x) std::cout << #x << ": " << x << "\n"
#define all(v) v.begin(), v.end()
#define li(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define endl '\n'
#define mem(name,val) memset(name,val,sizeof(name))
#define min(a,b) (a<=b ? a : b)
#define max(a,b) (a>=b ? a : b)
//using u64 = uint64_t;
//using u128 = __uint128_t;

const int nmax = 2025;
class DSU{
    public:
    int p[nmax],sz[nmax];
    stack<pii> his;
    stack<int> ss;
    void clear(){
        li(i,0,nmax){p[i]=i;sz[i]=1;}
        while(!his.empty())his.pop();
        while(!ss.empty())ss.pop();
    }
    DSU(){
        clear();
    }
    int get(int a){
        return p[a]==a?a:get(p[a]);
    }
    void uni(int a, int b){
        a=get(a);
        b=get(b);
        if(a==b)return;
        if(sz[a]<sz[b])swap(a,b);
        if(!ss.empty()){his.push({a,b});ss.top()++;};
        p[b]=a;
        sz[a]+=sz[b];
    }
    bool same(int a, int b){
        return get(a) == get(b);
    }
    void persist(){
        ss.push(0);
    }
    void rollback(){
        int numchg = ss.top(); ss.pop();
        li(_,0,numchg){
            auto h = his.top();his.pop();
            p[h.S] = h.S;
            sz[h.F]-=sz[h.S];
        }
    }
};

struct circ{
    ll x,y,r;
};

#define left 2004
#define bot 2005
#define rig 2003
#define top 2002

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,m,e;
    ll w,h,x,y,r;
    cin>>n>>m>>w>>h;
    circ trees[n];
    vector<pair<double,pii>> edg;
    DSU dsu;
    li(i,0,n){
        cin>>x>>y>>r;
        circ nc;
        nc.x = x; nc.y = y; nc.r = r;
        trees[i] = nc;
    }
    li(i,0,n){
        li(j,i+1,n){
            double dist = sqrt((trees[i].x-trees[j].x)*(trees[i].x-trees[j].x)+(trees[i].y-trees[j].y)*(trees[i].y-trees[j].y));
            dist -= (trees[i].r + trees[j].r);
            
            edg.pb({dist, mp(i,j)});
        }
        edg.pb({h-trees[i].y-trees[i].r, mp(top, i)});
        edg.pb({w-trees[i].x-trees[i].r, mp(rig,i)});
        edg.pb({trees[i].x-trees[i].r, mp(left,i)});
        edg.pb({trees[i].y-trees[i].r, mp(bot,i)});
    }
    sort(all(edg));
    vector<pair<int,pii>> q(m);
    li(i,0,m){
        cin>>r>>e;
        q[i] = mp(r,mp(e,i));
    }
    sort(all(q));
    int ind = 0;
    vector<vector<int>> ans(m);
    li(i,0,m){
        while(edg[ind].F < 2 * q[i].F){
            dsu.uni(edg[ind].S.F, edg[ind].S.S);
            ind++;
        }
        
        e = q[i].S.F;
        ans[q[i].S.S].pb(e);
        if((e == 1 and dsu.same(left,bot)) ||
           (e == 2 and dsu.same(rig,bot)) ||
           (e == 3 and dsu.same(top,rig)) ||
           (e == 4 and dsu.same(top,left))){continue;}
        if(e != 1 && !dsu.same(left,bot) && !((e==3 || e==4) && dsu.same(left,rig)) && !(e==2 && dsu.same(top,bot))) ans[q[i].S.S].pb(1);
        if(e != 2 && !dsu.same(rig,bot) && !((e==3 || e==4) && dsu.same(left,rig)) && !(e==1 && dsu.same(top,bot))) ans[q[i].S.S].pb(2);
        if(e != 3 && !dsu.same(rig,top) && !((e==1 || e==2) && dsu.same(left,rig)) && !(e==4 && dsu.same(top,bot))) ans[q[i].S.S].pb(3);
        if(e != 4 && !dsu.same(left,top) && !((e==1 || e==2) && dsu.same(left,rig)) && !(e==3 && dsu.same(top,bot))) ans[q[i].S.S].pb(4);
        sort(all(ans[q[i].S.S]));        
    }
    li(i,0,m){
        for(int dz:ans[i]){cout<<dz;}
        cout<<endl;
    }
    return 0;
}

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