Submission #493486

#TimeUsernameProblemLanguageResultExecution timeMemory
493486_Monkey_Ball Machine (BOI13_ballmachine)C++17
100 / 100
141 ms21164 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define el '\n' const int maxn=1e5+1,oo=1e9; void amin(int &x,int y){ if(x>y) x=y;} void amax(int &x,int y){ if(x<y) x=y;} int n,m,opt,o,cnt,k,u,val,ans; vector<vector<int>> con,far; vector<int> cha,minn,ut,reut,st; vector<bool> ok; // trade 1 bool check(int x,int y){ return minn[x]<minn[y]; } int prepare(int z){ minn[z]=z; for(int &e:con[z]) amin(minn[z],prepare(e)); return minn[z]; } void dfs(int z){ for(int &e:con[z]) dfs(e); cnt++; ut[z]=cnt; reut[cnt]=z; return; } void pre_up(int id,int l,int r){ if(r<u || l>u) return; if(l==r){ st[id]+=val; return; } int mid=(l+r)/2; pre_up(id*2,l,mid); pre_up(id*2+1,mid+1,r); st[id]=st[id*2]+st[id*2+1]; return; } void up(int id,int v){ u=id; val=v; return pre_up(1,1,n); } void pre_get(int id,int l,int r){ if(l==r){ ans=l; ok[l]=1; up(l,1); return; } int mid=(l+r)/2; if(mid-l+1==st[id*2]) pre_get(id*2+1,mid+1,r); else pre_get(id*2,l,mid); } void get(){ return pre_get(1,1,n); } // trade 2 int main(){ ios_base::sync_with_stdio(0);cin.tie(0); cin >> n >> m; con.resize(n+1); cha.resize(n+1); minn.resize(n+1); ut.resize(n+1); reut.resize(n+1); st.resize(n*4+1); ok.resize(n+1); far.resize(18,vector<int> (n+1)); for(int i=1;i<=n;++i){ cin >> cha[i]; con[ cha[i] ].push_back(i); } opt=con[0][0]; prepare(opt); for(int i=1;i<=n;++i) sort(con[i].begin(),con[i].end(),check); dfs(opt); for(int i=1;i<=n;++i) far[0][ut[i]]=ut[cha[i]]; for(int i=1;i<18;++i){ for(int j=1;j<=n;++j){ far[i][j]=far[i-1][ far[i-1][j] ]; } } while(m--){ cin >> o >> k; if(o==1){ for(int i=0;i<k;++i) get(); cout << reut[ans] << el; } else { cnt=0; k=ut[k]; for(int i=17;i>=0;--i) if(ok[ far[i][k] ]){ cnt+=(1<<i); k=far[i][k]; } up(k,-1); ok[k]=0; cout << cnt << el; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...