#include <bits/stdc++.h>
#define test ll t; cin >> t; while(t--)
typedef long long int ll;
const ll cons = 1e5 + 5;
using namespace std;
ll lev[cons];
ll mini[cons];
vector<ll> adj[cons];
ll pos[cons], cur = 0;
ll dp[cons][20], l = 19;
void dfs1(ll v, ll par){
lev[v] = (par != -1 ? lev[par] + 1 : 0);
for(ll i = 1; i <= l; i++){
if(dp[v][i - 1] == -1)
dp[v][i] = dp[v][i - 1];
else
dp[v][i] = dp[dp[v][i - 1]][i - 1];
}
mini[v] = v;
for(auto u : adj[v]){
if(u != par){
dfs1(u, v);
mini[v] = min(mini[v], mini[u]);
}
}
}
void dfs2(ll v, ll par){
vector<array<ll, 2>> order;
for(auto u : adj[v])
if(u != par)
order.push_back({mini[u], u});
sort(order.begin(), order.end());
for(auto [minu, u] : order){
dfs2(u, v);
}
pos[v] = cur++;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
ll n, q;
cin >> n >> q;
vector<ll> par(n);
for(auto &u : par)
cin >> u, u--;
ll root = -1;
for(ll i = 0; i < n; i++){
if(par[i] < 0)
root = i;
else {
adj[i].push_back(par[i]);
adj[par[i]].push_back(i);
}
}
for(ll i = 0; i < n; i++)
dp[i][0] = par[i];
dfs1(root, -1);
dfs2(root, -1);
// for(ll i = 0; i < n; i++)
// cout << pos[i] << " ";
// cout << "\n";
using pll = array<ll, 2>;
priority_queue<pll, vector<pll>, greater<pll>> pq;
for(ll i = 0; i < n; i++)
pq.push({pos[i], i});
vector<ll> check(n, 0);
while(q--){
ll t;
cin >> t; --t;
if(!t){
ll k;
cin >> k;
ll ans = -1;
while(k){
pll v = pq.top();
pq.pop();
check[v[1]] = 1;
ans = v[1];
k--;
}
cout << ++ans << "\n";
}
else {
ll v;
cin >> v; --v;
ll old_ = lev[v];
for(ll i = l; i >= 0; i--)
if(dp[v][i] != -1 && check[dp[v][i]])
v = dp[v][i];
ll new_ = lev[v];
check[v] = 0;
pq.push({pos[v], v});
cout << old_ - new_ << "\n";
}
}
cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2676 KB |
Output is correct |
2 |
Correct |
120 ms |
20668 KB |
Output is correct |
3 |
Correct |
82 ms |
20668 KB |
Output is correct |
4 |
Correct |
2 ms |
2676 KB |
Output is correct |
5 |
Correct |
3 ms |
2672 KB |
Output is correct |
6 |
Correct |
4 ms |
2892 KB |
Output is correct |
7 |
Correct |
3 ms |
2940 KB |
Output is correct |
8 |
Correct |
3 ms |
2944 KB |
Output is correct |
9 |
Correct |
8 ms |
3840 KB |
Output is correct |
10 |
Correct |
29 ms |
7120 KB |
Output is correct |
11 |
Correct |
127 ms |
20708 KB |
Output is correct |
12 |
Correct |
71 ms |
20700 KB |
Output is correct |
13 |
Correct |
105 ms |
20664 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
37 ms |
10872 KB |
Output is correct |
2 |
Correct |
176 ms |
37404 KB |
Output is correct |
3 |
Correct |
110 ms |
28912 KB |
Output is correct |
4 |
Correct |
53 ms |
13304 KB |
Output is correct |
5 |
Correct |
57 ms |
13504 KB |
Output is correct |
6 |
Correct |
77 ms |
13532 KB |
Output is correct |
7 |
Correct |
62 ms |
11456 KB |
Output is correct |
8 |
Correct |
31 ms |
10860 KB |
Output is correct |
9 |
Correct |
168 ms |
36592 KB |
Output is correct |
10 |
Correct |
177 ms |
37412 KB |
Output is correct |
11 |
Correct |
141 ms |
37364 KB |
Output is correct |
12 |
Correct |
174 ms |
32880 KB |
Output is correct |
13 |
Correct |
116 ms |
40096 KB |
Output is correct |
14 |
Correct |
83 ms |
28864 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
66 ms |
19736 KB |
Output is correct |
2 |
Correct |
189 ms |
32968 KB |
Output is correct |
3 |
Correct |
128 ms |
36456 KB |
Output is correct |
4 |
Correct |
112 ms |
29920 KB |
Output is correct |
5 |
Correct |
126 ms |
30592 KB |
Output is correct |
6 |
Correct |
174 ms |
30672 KB |
Output is correct |
7 |
Correct |
118 ms |
26972 KB |
Output is correct |
8 |
Correct |
136 ms |
36516 KB |
Output is correct |
9 |
Correct |
176 ms |
36936 KB |
Output is correct |
10 |
Correct |
180 ms |
37560 KB |
Output is correct |
11 |
Correct |
213 ms |
37556 KB |
Output is correct |
12 |
Correct |
191 ms |
32952 KB |
Output is correct |
13 |
Correct |
230 ms |
45184 KB |
Output is correct |
14 |
Correct |
114 ms |
28972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
169 ms |
36856 KB |
Output is correct |
2 |
Correct |
167 ms |
32864 KB |
Output is correct |
3 |
Correct |
155 ms |
44944 KB |
Output is correct |
4 |
Correct |
183 ms |
36800 KB |
Output is correct |
5 |
Correct |
191 ms |
37496 KB |
Output is correct |
6 |
Correct |
156 ms |
37516 KB |
Output is correct |
7 |
Correct |
163 ms |
32960 KB |
Output is correct |
8 |
Correct |
140 ms |
44968 KB |
Output is correct |
9 |
Correct |
86 ms |
28884 KB |
Output is correct |