Submission #1262252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262252		enzy	Ball Machine (BOI13_ballmachine)	C++20	100 / 100	431 ms	28096 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int maxk=22;
const int inf=1e9+7;
vector<pair<int,int>>v[maxn];
int pai[maxn], sub[maxn], tin[maxn], tout[maxn], val[maxn], dp[maxn][maxk], seg[4*maxn], lz[4*maxn], tmp, prof[maxn];
void dfs1(int u){
    sub[u]=u;
    for(pair<int,int> viz : v[u]){
        prof[viz.second]=prof[u]+1;
        dfs1(viz.second);
        sub[u]=min(sub[u],sub[viz.second]);
    }
}
void dfs2(int u){
    tin[u]=++tmp;
    for(pair<int,int> viz : v[u]) dfs2(viz.second);
    tout[u]=++tmp;
}
bool cmp(pair<int,pair<int,int>> a, pair<int,pair<int,int>> b){
    return a.second.second<b.second.second;
}
void refresh(int id, int ini, int fim){
    if(lz[id]==-1) return;
    if(ini!=fim){
        int e=2*id, d=2*id+1;
        lz[e]=lz[d]=lz[id];
    }
    seg[id]=(fim-ini+1)*lz[id];
    lz[id]=-1;
}
void update(int id, int ini, int fim, int l, int r, int x){
    refresh(id,ini,fim);
    if(ini>r||fim<l) return;
    if(l<=ini&&fim<=r){
        lz[id]=x;
        refresh(id,ini,fim);
        return;
    }
    int mid=(ini+fim)/2, e=2*id, d=2*id+1;
    update(e,ini,mid,l,r,x);
    update(d,mid+1,fim,l,r,x);
    seg[id]=seg[e]+seg[d];
}
int query(int id, int ini, int fim, int l, int r){
    refresh(id,ini,fim);
    if(ini>r||fim<l) return 0;
    if(l<=ini&&fim<=r) return seg[id];
    int mid=(ini+fim)/2, e=2*id, d=2*id+1;
    return query(e,ini,mid,l,r)+query(d,mid+1,fim,l,r);
}
int main(){
    int n, q, root; cin >> n >> q;
    for(int i=1;i<=n;i++){
        cin >> pai[i];
        if(!pai[i]){
            pai[i]=i;
            root=i;
        }else v[pai[i]].push_back({0,i});
        dp[i][0]=pai[i];
    }
    for(int k=1;k<maxk;k++)
        for(int i=1;i<=n;i++) dp[i][k]=dp[dp[i][k-1]][k-1];
    dfs1(root);
    for(int i=1;i<=n;i++){
        for(pair<int,int> &viz : v[i]) viz.first=sub[viz.second];
        sort(v[i].begin(),v[i].end());
    }
    dfs2(root);
    vector<pair<int,pair<int,int>>>process;
    for(int i=1;i<=n;i++) process.push_back({i,{tin[i],tout[i]}});
    sort(process.begin(),process.end(),cmp);
    for(int i=0;i<process.size();i++) val[process[i].first]=i+1;
    memset(seg,0,sizeof(seg)); memset(lz,-1,sizeof(lz));
    while(q--){
        int o, x; cin >> o >> x;
        if(o==1){
            int l=1, r=n;
            while(l<r){
                int mid=(l+r)/2;
                if(mid-query(1,1,n,1,mid)>=x) r=mid;
                else l=mid+1;
            }
            update(1,1,n,1,l,1);
            cout << process[l-1].first << endl;
        }else{
            int og=x;
            for(int k=maxk-1;k>=0;k--){
                int at=dp[x][k];
                if(query(1,1,n,val[at],val[at])) x=at;
            }
            cout << prof[og]-prof[x] << endl;
            update(1,1,n,val[x],val[x],0);
        }
    }
}

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