This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
int main(){
cin.tie(0)->sync_with_stdio(0);
int n, q;
cin >> n >> q;
vector<int> pai(n+1);
int root = 0;
matrix<int> g(n+1);
for(int i = 1; i <= n; i++){
cin >> pai[i];
if(pai[i]!=0){
g[pai[i]].push_back(i);
pai[i] = 0;
} else root = i;
}
vector<int> mn(n+1,1e9);
auto prec=[&](int id, auto dfs)->void{
mn[id] = id;
for(int i : g[id]){
dfs(i,dfs);
mn[id] = min(mn[id],mn[i]);
}
sort(all(g[id]),[&](int a, int b){
return mn[a] < mn[b];
});
};
prec(root,prec);
priority_queue<pii,vector<pii>,greater<pii>> pq;
int timer = -1;
vector<int> order(n+1);
auto dfs=[&](int id, auto dfs)->void{
for(int i : g[id]){
dfs(i,dfs);
}
order[id] = ++timer;
pq.push({order[id],id});
};
dfs(root,dfs);
while(q--){
int type, x;
cin >> type >> x;
if(type == 1){
int cur;
while(x--){
cur = pq.top().ss;
pq.pop();
for(int i : g[cur])
pai[i] = cur;
}
cout << cur << '\n';
} else {
int ct = 0;
while(pai[x]){
ct++;
x = pai[x];
}
for(int i : g[x])
pai[i] = 0;
pq.push({order[x],x});
cout << ct << '\n';
}
}
}
Compilation message (stderr)
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:71:28: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
71 | cout << cur << '\n';
| ^~~~
# | 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... |