Submission #1190054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190054		AlgorithmWarrior	Ball Machine (BOI13_ballmachine)	C++20	100 / 100	232 ms	27116 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;

int const LOG=20;
int const MAX=100005;
int n,q;
int tata[MAX];
vector<int>tree[MAX];
int root;
int tin[MAX],tout[MAX];
int minimsub[MAX];
int ord[MAX];
int id_ord[MAX];
int lift[MAX][LOG];
int h[MAX];

void read(){
    cin>>n>>q;
    int i;
    for(i=1;i<=n;++i){
        cin>>tata[i];
        if(tata[i])
            tree[tata[i]].push_back(i);
        else
            root=i;
    }
}

void minself(int& x,int val){
    if(x>val)
        x=val;
}

struct AIB{
    int v[MAX];
    int ub(int x){
        return x&(-x);
    }
    void add(int pos,int val){
        while(pos<=n){
            v[pos]+=val;
            pos+=ub(pos);
        }
    }
    int sum(int pos){
        int s=0;
        while(pos){
            s+=v[pos];
            pos-=ub(pos);
        }
        return s;
    }
    int bin_search(){
        int pos=0;
        int i;
        for(i=LOG;i>=0;--i)
            if(pos+(1<<i)<=n && v[pos+(1<<i)]==(1<<i))
                pos+=(1<<i);
        return pos+1;
    }
}ocup,mars;

bool crt(int fiu1,int fiu2){
    return minimsub[fiu1]<minimsub[fiu2];
}

void dfs1(int nod){
    minimsub[nod]=nod;
    static int time=0;
    tin[nod]=++time;
    for(auto fiu : tree[nod]){
        h[fiu]=h[nod]+1;
        dfs1(fiu);
        minself(minimsub[nod],minimsub[fiu]);
    }
    tout[nod]=time;
}

void dfs2(int nod){
    static int time=0;
    sort(tree[nod].begin(),tree[nod].end(),crt);
    for(auto fiu : tree[nod])
        dfs2(fiu);
    ord[++time]=nod;
    id_ord[nod]=time;
}

void init(){
    int i,j;
    for(i=1;i<=n;++i)
        lift[i][0]=tata[i];
    for(j=1;j<LOG;++j)
        for(i=1;i<=n;++i)
            lift[i][j]=lift[lift[i][j-1]][j-1];
    for(i=1;i<=n;++i){
        mars.add(tin[i],1);
        mars.add(tout[i]+1,-1);
    }
}

int bs_anc(int nod){
    int i;
    for(i=LOG-1;i>=0;--i)
        if(lift[nod][i] && mars.sum(tin[nod])==mars.sum(tin[tata[lift[nod][i]]]))
            nod=lift[nod][i];
    return nod;
}

void process_query(){
    int tip,nr;
    cin>>tip>>nr;
    if(tip==1){
        int ult=0;
        int i;
        for(i=1;i<=nr;++i){
            int poz=ocup.bin_search();
            ocup.add(poz,1);
            ult=ord[poz];
            mars.add(tin[ult],-1);
            mars.add(tout[ult]+1,1);
        }
        cout<<ult<<'\n';
    }
    else{
        int anc=bs_anc(nr);
        cout<<h[nr]-h[anc]<<'\n';
        ocup.add(id_ord[anc],-1);
        mars.add(tin[anc],1);
        mars.add(tout[anc]+1,-1);
    }
}

void process_queries(){
    int i;
    for(i=1;i<=q;++i)
        process_query();
}

int main()
{
    read();
    dfs1(root);
    dfs2(root);
    init();
    process_queries();
    return 0;
}

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