Submission #536447

#	Time	Username	Problem	Language	Result	Execution time	Memory
536447		__Variatto	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	331 ms	39068 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], pch[2*S+10];
void pchaj(int v, int pocz, int kon){
    t[v*2]+=(kon-pocz+1)/2*pch[v], t[v*2+1]+=(kon-pocz+1)/2*pch[v], pch[2*v]+=pch[v], pch[2*v+1]+=pch[v];
    pch[v]=0;
}
void Insert(int v, int pocz, int kon, int a, int b, int w){
    if(pocz>b||kon<a) return;
    if(a<=pocz&&kon<=b){
        pch[v]+=w;
        t[v]+=(kon-pocz+1)*w;
        return;
    }
    pchaj(v, pocz, kon);
    Insert(v*2, pocz, (pocz+kon)/2, a, b, w);
    Insert(v*2+1, (pocz+kon)/2+1, kon, a, b, w);
    t[v]=t[v*2]+t[v*2+1];
}
int Query(int v, int pocz, int kon, int a){
    if(kon<a||pocz>a) return 0;
    if(pocz==kon && kon==a) return t[v];
    pchaj(v, pocz, kon);
    return (Query(v*2, pocz, (pocz+kon)/2, a)+Query(v*2+1, (pocz+kon)/2+1, kon, a));
}
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(1, 0, S-1, 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(1, 0, S-1, pre[b]);
            cout<<wyn<<"\n";
            int l=0, v=b;
            while(wyn){
                if(wyn%2)
                    v=jump[v][l];
                wyn/=2, l++;
            }
            Insert(1, 0, S-1, 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