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>
using namespace std;
#define int long long
#define endl '\n'
#define F first
#define S second
const int N = 1e5 + 15, LOG = 19;
int n, q, par[LOG][N], zr[N], sv[N], t = 1, root;
unordered_map<int, int> mp;
vector<int> adj[N];
bool ch[N];
set<int> s;
void ip() {
cin >> n >> q;
for (int i = 1; i <= n; i++) {
zr[i] = i;
int p;
cin >> p;
par[0][i] = p;
adj[p].push_back(i);
if (p == 0)
root = i;
}
}
void fix_par() {
for (int j = 1; j < LOG; j++)
for (int i = 1; i <= n; i++)
par[j][i] = par[j - 1][par[j - 1][i]];
}
void dfs(int v) {
for (auto u : adj[v]) {
dfs(u);
zr[v] = min(zr[v], zr[u]);
}
}
void fdfs(int v) {
for (auto u : adj[v])
fdfs(u);
sv[v] = t;
mp[t] = v;
s.insert(t);
t++;
}
bool cmp(int i, int j) {
return (zr[i] < zr[j]);
}
void fix() {
for (int i = 1; i <= n; i++)
sort(adj[i].begin(), adj[i].end(), cmp);
/* for (int i = 1; i <= n; i++) {
cout << i << " : ";
for (auto v : adj[i])
cout << v << " ";
cout << endl;
}*/
}
pair<int, int> get_par(int v) {
int cnt = 0;
for (int i = LOG - 1; ~i; i--) {
if (ch[par[i][v]]) {
cnt += (1 << i);
v = par[i][v];
}
}
return (make_pair(cnt, v));
}
void query() {
while (q--) {
int qu, f;
cin >> qu;
if (qu == 1) {
cin >> f;
int v;
while (f--) {
v = mp[*s.begin()];
s.erase(s.begin());
ch[v] = true;
// cout << v << " ";
}
// cout << endl;
cout << v << endl;
}
else {
cin >> f;
pair<int, int> ans = get_par(f);
// cout << ans.F << " " << ans.S << endl;
ch[ans.S] = false;
s.insert(sv[ans.S]);
cout << ans.F << endl;
}
}
}
void run() {
ip();
fix_par();
dfs(root);
fix();
fdfs(root);
query();
}
signed main() {
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
run();
}
# | 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... |