This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//i_love_aisukiuwu
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "/home/trucmai/.vim/tools.h"
#define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define debug(x...)
#endif
void open(){
if(fopen("i.inp","r")){
freopen("i.inp","r",stdin);
freopen("o.out","w",stdout);
}
}
#define ll long long
#define all(a) (a).begin(), (a).end()
#define vi vector<ll>
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define fi first
#define se second
#define gcd __gcd
#define mset(a,v) memset(a, v, sizeof(a))
#define endl '\n'
#define spc " "
const int MN1 = 1e5 + 5,MN2 = 1e4 + 5,LOG = 27;
const ll MOD = 1e9 + 7,INF = 1e9;
ll n,q,p[MN1],root;
ll mx[MN1],h[MN1],sz[MN1];
ll up[MN1][LOG];
bool col[MN1];
vector<ll>adj[MN1];
ll timer = 0;
void dfs(ll u,ll pre){
mx[u] = u; sz[u] = 1;
for(ll v : adj[u]){
if(v == pre) continue;
h[v] = h[u] + 1;
up[v][0] = u;
for(ll i = 1;i < LOG;++i) up[v][i] = up[up[v][i-1]][i-1];
dfs(v,u);
mx[u] = min(mx[u],mx[v]);
sz[u] += sz[v];
}
}
ll dfs_upd(ll u,ll cnt){
for(ll &v : adj[u]){
if(!col[v]){
ll tmp = min(cnt,sz[v]),
x = dfs_upd(v,tmp);
if(cnt == tmp) return x;
}
}
if(cnt > 0) --cnt,col[u] = true;
return u;
}
void solve(){
cin>>n>>q;
for(ll i = 1;i <= n;++i){
cin>>p[i];
if(p[i] == 0){root = i; continue;}
adj[p[i]].push_back(i);
}
dfs(root,0);
while(q--){
ll t,u; cin>>t>>u;
if(t == 1) cout<<dfs_upd(root,u)<<endl;
else{
ll v = u;
for(ll i = LOG;i >= 0;--i)
if(col[up[v][i]]) v = up[v][i];
col[v] = false;
cout<<h[u] - h[v]<<endl;
}
}
}
signed main(){
cin.tie(0) -> sync_with_stdio(0);
open();
ll t = 1; //cin>>t;
while(t--) solve();
cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
Compilation message (stderr)
ballmachine.cpp: In function 'void open()':
ballmachine.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
14 | freopen("i.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
ballmachine.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
15 | freopen("o.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |