Submission #1133717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133717		kitkat12	Park (BOI16_park)	C++20	0 / 100	2592 ms	468 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{
    int 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,w,h,x,y,r,e;
    cin>>n>>m>>w>>h;
    circ trees[n];
    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(_,0,m){
        cin>>r>>e;
        dsu.persist();
        li(i,0,n){
            li(j,0,n){
                if(i==j) continue;
                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);
                if(dist < 2*r){
                    dsu.uni(i,j);
                }
            }
            if(h-trees[i].y-trees[i].r<2*r){dsu.uni(i,top);} // top
            else if(w-trees[i].x-trees[i].r<2*r){dsu.uni(i,rig);} // right
            else if(trees[i].x-trees[i].r<2*r){dsu.uni(i,left);} // left
            else if(trees[i].y-trees[i].r<2*r){dsu.uni(i,bot);} // bottom
        }
        vector<int> k;
        k.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))){ goto jmp;}
        if(e != 1 && !dsu.same(left,bot) && !((e==3 || e==4) && dsu.same(left,rig)) && !(e==2 && dsu.same(top,bot))) k.pb(1);
        if(e != 2 && !dsu.same(rig,bot) && !((e==3 || e==4) && dsu.same(left,rig)) && !(e==1 && dsu.same(top,bot))) k.pb(2);
        if(e != 3 && !dsu.same(rig,top) && !((e==1 || e==2) && dsu.same(left,rig)) && !(e==4 && dsu.same(top,bot))) k.pb(3);
        if(e != 4 && !dsu.same(left,top) && !((e==1 || e==2) && dsu.same(left,rig)) && !(e==3 && dsu.same(top,bot))) k.pb(4);
        sort(all(k));
        jmp:
        for(int dz:k){cout<<dz;}
        cout<<endl;

        dsu.rollback();
    }
    return 0;
}

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