#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
using namespace std;
template<typename Lhs, typename Rhs> inline void Max_self(Lhs &a, Rhs b) { a = (a > b ? a : b); }
template<typename Lhs, typename Rhs> inline void Min_self(Lhs &a, Rhs b) { a = (a < b ? a : b); }
const int N = 1e5 + 10;
void dfs_more_and_more(int u);
void dfs_calc(int u);
void pre_calc();
int first_parent(int u);
int n, q;
vector<int> g[N];
int root;
int Lg, dist[N], parent[20][N];
bool have[N];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int cnt, in[N];
int dp[N];
void dfs_more_and_more(int u) {
dp[u] = u;
for(auto v : g[u]) {
dist[v] = dist[u] + 1;
parent[0][v] = u;
dfs_more_and_more(v);
Min_self(dp[u], dp[v]);
}
}
void dfs_calc(int u) {
sort(g[u].begin(), g[u].end(), [&] (int lhs, int rhs) {
if(dp[lhs] != dp[rhs]) return dp[lhs] < dp[rhs];
return lhs < rhs;
});
for(auto v : g[u]) dfs_calc(v);
in[u] = ++ cnt;
pq.push(make_pair(in[u], u));
}
int first_parent(int u) {
for(int i = Lg; i >= 0; -- i)
if(have[parent[i][u]] & 1) u = parent[i][u];
return u;
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if (fopen("Ball.inp", "r")) {
freopen("Ball.inp", "r", stdin);
freopen("Ball.out", "w", stdout);
}
cin >> n >> q;
for(int v = 1; v <= n; ++ v) {
int u; cin >> u;
if(u == 0) root = v;
else g[u].push_back(v);
// cout << u << ' ' << v << '\n';
}
pre_calc();
while(q--) {
int type; cin >> type;
if(type == 1) {
int k; cin >> k;
while(k--) {
auto psy = pq.top(); pq.pop();
have[psy.second] = true;
if(k == 0) cout << psy.second;
}
}
else {
int u; cin >> u;
int p = first_parent(u);
have[p] = false;
pq.push(make_pair(in[p], p));
// cout << u << ' ' << p << ' ';
cout << dist[u] - dist[p];
}
cout << '\n';
}
return 0;
}
void pre_calc() {
dfs_more_and_more(root);
dfs_calc(root);
Lg = __lg(n);
for(int j = 1; j <= Lg; ++ j)
for(int i = 1; i <= n; ++ i)
parent[j][i] = parent[j - 1][parent[j - 1][i]];
}
/// Code by vuavisao
Compilation message
ballmachine.cpp: In function 'int32_t main()':
ballmachine.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | freopen("Ball.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | freopen("Ball.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
141 ms |
10628 KB |
Output is correct |
3 |
Correct |
41 ms |
10564 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2684 KB |
Output is correct |
6 |
Correct |
2 ms |
2772 KB |
Output is correct |
7 |
Correct |
2 ms |
2772 KB |
Output is correct |
8 |
Correct |
3 ms |
2820 KB |
Output is correct |
9 |
Correct |
9 ms |
3156 KB |
Output is correct |
10 |
Correct |
16 ms |
4616 KB |
Output is correct |
11 |
Correct |
90 ms |
10580 KB |
Output is correct |
12 |
Correct |
44 ms |
10564 KB |
Output is correct |
13 |
Correct |
87 ms |
10660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
7052 KB |
Output is correct |
2 |
Correct |
186 ms |
18804 KB |
Output is correct |
3 |
Correct |
56 ms |
14016 KB |
Output is correct |
4 |
Correct |
58 ms |
8044 KB |
Output is correct |
5 |
Correct |
56 ms |
7924 KB |
Output is correct |
6 |
Correct |
55 ms |
7848 KB |
Output is correct |
7 |
Correct |
59 ms |
7052 KB |
Output is correct |
8 |
Correct |
26 ms |
7056 KB |
Output is correct |
9 |
Correct |
152 ms |
19264 KB |
Output is correct |
10 |
Correct |
157 ms |
18916 KB |
Output is correct |
11 |
Correct |
143 ms |
19068 KB |
Output is correct |
12 |
Correct |
153 ms |
16736 KB |
Output is correct |
13 |
Correct |
65 ms |
21572 KB |
Output is correct |
14 |
Correct |
56 ms |
13996 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
11104 KB |
Output is correct |
2 |
Correct |
148 ms |
17024 KB |
Output is correct |
3 |
Correct |
88 ms |
19776 KB |
Output is correct |
4 |
Correct |
80 ms |
15988 KB |
Output is correct |
5 |
Correct |
91 ms |
15648 KB |
Output is correct |
6 |
Correct |
78 ms |
15584 KB |
Output is correct |
7 |
Correct |
80 ms |
14096 KB |
Output is correct |
8 |
Correct |
78 ms |
19752 KB |
Output is correct |
9 |
Correct |
136 ms |
19516 KB |
Output is correct |
10 |
Correct |
143 ms |
19028 KB |
Output is correct |
11 |
Correct |
180 ms |
19052 KB |
Output is correct |
12 |
Correct |
147 ms |
17088 KB |
Output is correct |
13 |
Correct |
160 ms |
24312 KB |
Output is correct |
14 |
Correct |
134 ms |
14528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
157 ms |
19512 KB |
Output is correct |
2 |
Correct |
185 ms |
17096 KB |
Output is correct |
3 |
Correct |
72 ms |
23880 KB |
Output is correct |
4 |
Correct |
139 ms |
19520 KB |
Output is correct |
5 |
Correct |
153 ms |
19136 KB |
Output is correct |
6 |
Correct |
120 ms |
19012 KB |
Output is correct |
7 |
Correct |
141 ms |
17096 KB |
Output is correct |
8 |
Correct |
69 ms |
23864 KB |
Output is correct |
9 |
Correct |
61 ms |
14004 KB |
Output is correct |