Submission #521163

#	Time	Username	Problem	Language	Result	Execution time	Memory
521163		krit3379	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	344 ms	33872 KiB

ballmachine

#include<bits/stdc++.h>
using namespace std;
#define N 100005

int t[4*N],lazy[4*N];
int root,bp[20][N],h[N],st[N],en[N],sub_sz[N],sub_mi[N],prior[N],sz,p,ll,rr,val;
vector<int> g[N];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;

void push(int x){
    if(lazy[x]){
        t[x*2]=t[x*2+1]=lazy[x*2]=lazy[x*2+1]=lazy[x];
        lazy[x]=0;
    }
}

void update(int x,int l,int r){
    if(r<ll||rr<l)return ;
    if(ll<=l&&r<=rr){
        t[x]=val;
        lazy[x]=val;
        return ;
    }
    push(x);
    int mid=(l+r)/2;
    update(x*2,l,mid);
    update(x*2+1,mid+1,r);
}

int sol(int x,int l,int r){
    if(r<ll||rr<l)return -1;
    if(ll<=l&&r<=rr)return t[x];
    push(x);
    int mid=(l+r)/2;
    return max(sol(x*2,l,mid),sol(x*2+1,mid+1,r));
}

void dfs(int s,int f){
    bp[0][s]=f;
    st[s]=en[s]=++sz;
    sub_sz[s]=1;
    sub_mi[s]=s;
    h[s]=h[f]+1;
    for(auto x:g[s]){
        dfs(x,s);
        en[s]=en[x];
        sub_mi[s]=min(sub_mi[s],sub_mi[x]);
        sub_sz[s]+=sub_sz[x];
    }
}

void up_pri(int s){
    vector<pair<int,int>> temp;
    for(auto x:g[s])temp.push_back({sub_mi[x],x});
    sort(temp.begin(),temp.end());
    for(auto x:temp){
        up_pri(x.second);
    }
    prior[s]=++p;
}

int main(){
    int n,m,i,j,op,k,x;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&k);
        g[k].push_back(i);
        if(k==0)root=i;
    }
    dfs(root,0);
    up_pri(root);
    for(i=1;i<=n;i++)q.push({prior[i],i});
    for(i=1;i<20;i++)for(j=1;j<=n;j++)bp[i][j]=bp[i-1][bp[i-1][j]];
    while(m--){
        scanf("%d %d",&op,&k);
        if(op==1){
            while(k--){
                x=q.top().second;
                q.pop();
                ll=st[x],rr=en[x];
                val=h[x];
                update(1,1,n);
            }
            printf("%d\n",x);
        }
        else{
            ll=rr=st[k];
            val=sol(1,1,n);
            printf("%d\n",h[k]-val);
            if(h[k]!=val){
                for(i=19;i>=0;i--)if(h[bp[i][k]]>val)k=bp[i][k];
                k=bp[0][k];
            }
            q.push({prior[k],k});
            ll=st[k],rr=en[k];
            val=h[k]+1;
            update(1,1,n);
            ll=st[k],rr=st[k];
            val=0;
            update(1,1,n);
        }
    }

    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
ballmachine.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         scanf("%d",&k);
      |         ~~~~~^~~~~~~~~
ballmachine.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         scanf("%d %d",&op,&k);
      |         ~~~~~^~~~~~~~~~~~~~~~

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