Submission #859328

#	Time	Username	Problem	Language	Result	Execution time	Memory
859328		8pete8	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	146 ms	47044 KiB

ballmachine

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
#include<list>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
//#define p push
#define pb push_back
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
#define int long long
const int mxn=1e5,mod=69,lg=30,root=80,inf=1e18;
vector<int>adj[mxn+10];
int up[mxn+10][lg+5],h[mxn+10],st,id[mxn+10],mnsub[mxn+10];
bitset<mxn+10>on,del;
int ch=0,cnt=0;
bool cmp(int a,int b){return mnsub[a]<mnsub[b];}
void dfs(int cur){
    mnsub[cur]=cur;
    for(auto i:adj[cur]){
        h[i]=h[cur]+1;
        dfs(i);
        mnsub[cur]=min(mnsub[cur],mnsub[i]);
    }
    sort(all(adj[cur]),cmp);
}
priority_queue<pii,vector<pii>,greater<pii>>pq;
void dfs2(int cur){
    for(auto i:adj[cur])dfs2(i);
    id[cur]=cnt++;
    if(adj[cur].size()==0)pq.push({id[cur],cur});
}
int32_t main(){
    fastio
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        int a;cin>>a;
        if(a==0){
            st=i;
            continue;
        }
        adj[a].pb(i);
        up[i][0]=a;
    }
    dfs(st);
    dfs2(st);
    for(int j=1;j<=lg;j++)for(int i=1;i<=n;i++)up[i][j]=up[up[i][j-1]][j-1];
    while(m--){
        int t;cin>>t;
        if(t==1){
            int k;cin>>k;
            int ans=0;
            for(int i=0;i<k;i++){
                while(!pq.empty()&&on[pq.top().s])pq.pop();
                while(!pq.empty()&&del[pq.top().s]){
                    del[pq.top().s]=false;
                    pq.pop();
                }
                int cur=pq.top().s;
                pq.pop();
                ans=cur;
                on[cur]=true;
                pq.push({id[up[cur][0]],up[cur][0]});
            }
            cout<<ans<<'\n';
        }
        else{
            int x;cin>>x;
            int y=x;
            for(int i=lg;i>=0;i--)if(on[up[x][i]])x=up[x][i];
            on[x]=false;
            del[up[x][0]]=true;
            pq.push({id[x],x});
            cout<<h[y]-h[x]<<'\n';
        }
    }
}

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