#include "bits/stdc++.h"
using namespace std;
#define int long long
#define sz(v) ((int)(v).size())
#define all(a) (a).begin(), (a).end()
#define rall(a) a.rbegin(), a.rend()
#define F first
#define S second
#define time (double)clock() / (double)CLOCKS_PER_SEC
using pii = pair<int, int>;
using ll = long long;
using ld = long double;
const ll infll = (ll)4e18 + 27;
const ll inf = (ll)1e9 + 27;
const ll mod = (ll)1e9 + 7;
#ifdef home
#define dbg(x) cout << #x << " = " << (x) << endl
#else
#define dbg(x) 228
#endif
template <class T>
using pq = priority_queue <T, vector <T>, less <T>>;
template <class T>
using pqr = priority_queue <T, vector <T>, greater <T>>;
template <typename T, typename T2>
istream& operator>> (istream& in, pair<T, T2>& b) {
in >> b.first >> b.second;
return in;
}
template <typename T, typename T2>
ostream& operator<< (ostream& out, const pair<T, T2>& b) {
out << "{" << b.first << ", " << b.second << "}";
return out;
}
template <typename T>
istream& operator>> (istream& in, vector<T>& b) {
for(auto &v: b) {
in >> v;
}
return in;
}
template <typename T>
ostream& operator<< (ostream& out, vector<T>& b) {
for(auto &v: b) {
out << v << ' ';
}
return out;
}
template <typename T>
ostream& operator<< (ostream& out, deque<T>& b) {
for(auto &v: b) {
out << v << ' ';
}
return out;
}
template <typename T>
void print(T x, string end = "\n") {
cout << x << end;
}
template <typename T1, typename T2> bool chkmin(T1 &x, const T2 &y) { return x > y && (x = y, true); }
template <typename T1, typename T2> bool chkmax(T1 &x, const T2 &y) { return x < y && (x = y, true); }
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N = 1e5 + 10, LOG = 20;
int up[N][LOG];
vector<int> g[N];
set<pii> st;
int timer[N], cur = 1;
bool ok[N];
int h[N];
int calc(int u){
int mn = inf;
vector<pii> nw;
for(int i = 0;i < sz(g[u]);i++){
int x = calc(g[u][i]);
nw.push_back({x, g[u][i]});
mn = min(mn, x);
}
sort(all(nw));
g[u].clear();
for(auto [x, y]: nw){
g[u].push_back(y);
}
mn = min(mn, u);
return mn;
}
void dfs(int u, int p = -1){
h[u] = (p == -1 ? 0 : h[p] + 1);
for(int i = 0;i < LOG - 1;i++){
up[u][i + 1] = up[up[u][i]][i];
}
for(auto v: g[u]){
up[v][0] = u;
dfs(v, u);
}
timer[u] = cur++;
st.insert({timer[u], u});
}
int add(int k){
int last = -1;
for(int i = 0;i < k;i++){
auto [x, y] = *st.begin();
st.erase(st.begin());
last = y;
ok[y] = true;
}
return last;
}
int remove(int k){
int doll = 0;
int u = k;
int t = up[u][LOG - 1];
if(ok[t]){
ok[t] = false;
st.insert({timer[t], t});
return h[k];
}
for(int i = LOG - 1;i >= 0;i--){
if(ok[up[u][i]]){
u = up[u][i];
doll += (1ll << i);
}
}
if(u == k){
ok[u] = false;
st.insert({timer[u], u});
return 0;
}
ok[u] = false;
st.insert({timer[u], u});
return doll;
}
void solve() {
int n, q;
cin >> n >> q;
int root = 0;
for(int i = 1;i <= n;i++){
int x;
cin >> x;
if(x == 0){
root = i;
} else {
g[x].push_back(i);
}
}
calc(root);
up[root][0] = root;
dfs(root);
while (q--){
int t, k;
cin >> t >> k;
if(t == 1){
cout << add(k) << endl;
} else {
cout << remove(k) << endl;
}
}
}
int32_t main() {
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cout << fixed << setprecision(15);
int32_t t = 1;
//cin >> t;
#ifndef home
//freopen("fcount.in", "r", stdin);
//freopen("fcount.out", "w", stdout);
#endif
while(t--)
solve();
#ifdef home
cout << "_________________________________" << endl;
cout << "finished in " << time << " s";
#endif
return 0;
}
/*
8 18
2
0
1
1
3
3
4
6
1 8
2 8
2 8
2 8
2 8
2 8
2 7
2 7
2 5
1 8
2 8
2 8
2 8
2 8
2 8
2 7
2 7
2 5
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
270 ms |
19308 KB |
Output is correct |
3 |
Correct |
193 ms |
19444 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
4 ms |
2944 KB |
Output is correct |
7 |
Correct |
4 ms |
2900 KB |
Output is correct |
8 |
Correct |
4 ms |
2900 KB |
Output is correct |
9 |
Correct |
17 ms |
3668 KB |
Output is correct |
10 |
Correct |
47 ms |
6852 KB |
Output is correct |
11 |
Correct |
240 ms |
19348 KB |
Output is correct |
12 |
Correct |
202 ms |
19496 KB |
Output is correct |
13 |
Correct |
222 ms |
19340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
159 ms |
10044 KB |
Output is correct |
2 |
Correct |
309 ms |
34868 KB |
Output is correct |
3 |
Correct |
213 ms |
27868 KB |
Output is correct |
4 |
Correct |
151 ms |
12540 KB |
Output is correct |
5 |
Correct |
182 ms |
12748 KB |
Output is correct |
6 |
Correct |
155 ms |
12264 KB |
Output is correct |
7 |
Correct |
165 ms |
10784 KB |
Output is correct |
8 |
Correct |
156 ms |
10060 KB |
Output is correct |
9 |
Correct |
290 ms |
35108 KB |
Output is correct |
10 |
Correct |
318 ms |
34652 KB |
Output is correct |
11 |
Correct |
280 ms |
34876 KB |
Output is correct |
12 |
Correct |
309 ms |
30916 KB |
Output is correct |
13 |
Correct |
239 ms |
37492 KB |
Output is correct |
14 |
Correct |
225 ms |
27776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
154 ms |
18916 KB |
Output is correct |
2 |
Correct |
320 ms |
31792 KB |
Output is correct |
3 |
Correct |
231 ms |
34348 KB |
Output is correct |
4 |
Correct |
225 ms |
28844 KB |
Output is correct |
5 |
Correct |
221 ms |
28376 KB |
Output is correct |
6 |
Correct |
208 ms |
28324 KB |
Output is correct |
7 |
Correct |
223 ms |
25880 KB |
Output is correct |
8 |
Correct |
241 ms |
34288 KB |
Output is correct |
9 |
Correct |
340 ms |
35340 KB |
Output is correct |
10 |
Correct |
346 ms |
34908 KB |
Output is correct |
11 |
Correct |
418 ms |
34860 KB |
Output is correct |
12 |
Correct |
386 ms |
31792 KB |
Output is correct |
13 |
Correct |
444 ms |
42324 KB |
Output is correct |
14 |
Correct |
315 ms |
28256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
372 ms |
35352 KB |
Output is correct |
2 |
Correct |
400 ms |
31856 KB |
Output is correct |
3 |
Correct |
310 ms |
42188 KB |
Output is correct |
4 |
Correct |
372 ms |
35368 KB |
Output is correct |
5 |
Correct |
311 ms |
34944 KB |
Output is correct |
6 |
Correct |
315 ms |
34800 KB |
Output is correct |
7 |
Correct |
353 ms |
31812 KB |
Output is correct |
8 |
Correct |
260 ms |
42132 KB |
Output is correct |
9 |
Correct |
213 ms |
27864 KB |
Output is correct |