Submission #536451

#	Time	Username	Problem	Language	Result	Execution time	Memory
536451		__Variatto	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	317 ms	36872 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=1e5+10, S=1<<19, L=19;
int n, q, a, b, mini[MAX], root, nr[MAX];
vector<int>g[MAX];
int pre[MAX], maxiPre[MAX], jump[MAX][L+1], czas=1;
void dfs1(int v, int oj){
    mini[v]=v;
    pre[v]=czas++;
    maxiPre[v]=pre[v];
    jump[v][0]=oj;
    for(int i=1; i<=L; i++)
        jump[v][i]=jump[jump[v][i-1]][i-1];
    for(auto s:g[v]){
        if(s!=oj){
            dfs1(s, v);
            mini[v]=min(mini[v], mini[s]);
            maxiPre[v]=max(maxiPre[v], maxiPre[s]);
        }
    }
}
int akt=1;
void dfs2(int v, int oj){
    int aktMini=MAX;
    set<pair<int,int>>x;
    for(auto s: g[v])
        if(s!=oj)
            x.insert({mini[s], s});
    for(set<pair<int,int>>::iterator it=x.begin(); it!=x.end(); it++)
        dfs2((*it).se, v);

    nr[v]=akt++;
}
int t[2*S+10];
void Insert(int a, int b,int x){
    a+=S-1, b+=S+1;
    while(a+1<b){
        if(a%2==0) t[a+1]+=x;
        if(b%2==1) t[b-1]+=x;
        a/=2, b/=2;
    }
}
int Query(int pos){
    int res=0;
    pos+=S;
    while(pos){
        res+=t[pos];
        pos/=2;
    }
    return res;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n>>q;
    for(int i=1; i<=n; i++){
        cin>>a;
        if(!a)
            root=i;
        else
            g[i].pb(a), g[a].pb(i);
    }
    dfs1(root, root);
    dfs2(root, root);
    set<pair<int,int>>kol;
    for(int i=1; i<=n; i++)
        kol.insert({nr[i], i});
    while(q--){
        cin>>a>>b;
        if(a==1){
            while(b--){
                int v=(*kol.begin()).se;
                kol.erase(kol.begin());
                if(pre[v]+1<=maxiPre[v])
                    Insert(pre[v]+1, maxiPre[v], 1);
                if(!b)
                    cout<<v<<"\n";
            }
/*            for(int i=1; i<=n; i++)
                cout<<i<<" "<<pre[i]<<" "<<Query(1, 0, S-1, pre[i])<<"x\n";;
            cout<<"\n";
*/        }
        else{
            int wyn=Query(pre[b]);
            cout<<wyn<<"\n";
            int l=0, v=b;
            while(wyn){
                if(wyn%2)
                    v=jump[v][l];
                wyn/=2, l++;
            }
            Insert(pre[v]+1, maxiPre[v], -1);
            kol.insert({nr[v], v});
        }
    }
    
}

Compilation message (stderr)

ballmachine.cpp: In function 'void dfs2(int, int)':
ballmachine.cpp:28:9: warning: unused variable 'aktMini' [-Wunused-variable]
   28 |     int aktMini=MAX;
      |         ^~~~~~~

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