Submission #520283

#	Time	Username	Problem	Language	Result	Execution time	Memory
520283		niloyroot	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	527 ms	39032 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pl = pair<ll,ll>;
#define pb push_back
#define form(m,it) for(auto it=m.begin(); it!=m.end(); it++)
#define forp(i,a,b) for(ll i=a; i<=b; i++)
#define forn(i,a,b) for(ll i=a; i>=b; i--)
#define newl '\n'
#define ff first
#define ss second
const ll mod = 998244353;
const ll maxn = 1e5 + 5;
ll lgn;
ll up[maxn][20];
vi adj[maxn];
ll occur[maxn];
bool col[maxn];
vi euler;
ll sub[maxn];
ll depth[maxn];

void order(ll i, ll pa){
    sub[i]=i;
    for(auto u:adj[i]){
        if(u!=pa){
            order(u,i);
            sub[i]=min(sub[i],sub[u]);
        }
    }
}

void dfs(ll i, ll pa){
    up[i][0]=pa;
    forp(j,1,lgn){
        up[i][j]=up[up[i][j-1]][j-1];
    }
    for(auto u:adj[i]){
        if(u!=pa){
            depth[u]=depth[i]+1;
            dfs(u,i);
        }
    }
    euler.pb(i);
    occur[i]=euler.size();
}

ll find_anc(ll u, ll k){
    ll ind=0;
    while(k>0){
        if(k%2==1){
            u=up[u][ind];
        }
        ind++;
        k/=2;
    }
    return u;
}

void solve(){
    ll n,q; cin>>n>>q;
    ll root; lgn=ceil(log2(n));
    forp(i,1,n){
        ll p; cin>>p;
        if(p==0){
            root=i;
        } else {
            adj[i].pb(p);
            adj[p].pb(i);
        }
    }
    order(root,0);

    forp(i,1,n){
        sort(adj[i].begin(), adj[i].end(), [](ll u, ll v){
            return sub[u]<sub[v];
        });
    }

    dfs(root,root);

    set<pl> s;
    forp(i,1,n){
        s.insert({occur[i],i});
    }

    forp(i,1,q){
        ll t,x; cin>>t>>x;
        if(t==1){
            pl node;
            while(x--){
                node = *s.begin();
                col[node.ss]=1;
                s.erase(s.begin());
            }
            cout<<node.ss<<newl;
        } else {
            ll l=0,r=depth[x];
            while(l<r){
                ll mid=(l+r+1)>>1;
                if(col[find_anc(x,mid)]){
                    l=mid;
                } else {
                    r=mid-1;
                }
            }
            ll ans=find_anc(x,l);
            cout<<depth[x]-depth[ans]<<newl;
            col[ans]=0;
            s.insert({occur[ans],ans});
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1; //cin>>t;
    while(t--)solve();
}

Compilation message (stderr)

ballmachine.cpp: In function 'void solve()':
ballmachine.cpp:81:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |     dfs(root,root);
      |     ~~~^~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5