#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()
const int N = 1e5 + 12, M = 20, SQ = 320;
vector<int> g[N];
int n, q, t, f[N], p[N], par[M][N], root, d[N], h[N], sum[SQ];
bool dp[SQ], a[SQ * SQ + 12];
void ip() {
cin >> n >> q;
for (int i = 0; i < n; i++) {
int u;
cin >> u;
u--;
par[0][i] = u;
if (u == -1)
root = i;
else {
g[u].pb(i);
g[i].pb(u);
}
}
par[0][root] = root;
}
void dfs1(int u) {
d[u] = u;
for (auto i: g[u])
if (i != par[0][u]) {
h[i] = h[u] + 1;
dfs1(i);
d[u] = min(d[u], d[i]);
}
}
void dfs2(int u) {
vector<pii> tmp;
for (auto i: g[u])
if (i != par[0][u])
tmp.pb({d[i], i});
sort(all(tmp));
for (auto i: tmp)
dfs2(i.S);
f[t] = u;
p[u] = t;
t++;
}
void pre() {
dfs1(root);
dfs2(root);
for (int i = 1; i < M; i++)
for (int j = 0; j < n; j++)
par[i][j] = par[i - 1][par[i - 1][j]];
}
void add(int x) {
for (int i = 0; (i + 1) * SQ - 1 < x; i++) {
sum[i] = SQ;
dp[i] = true;
}
if (!dp[x / SQ])
for (int i = (x / SQ) * SQ; i <= x; i++)
if (!a[i]) {
a[i] = true;
sum[x / SQ]++;
}
}
void rem(int x) {
if (dp[x / SQ]) {
fill(a + x - x % SQ, a + x - x % SQ + SQ, 1);
sum[x / SQ] = SQ - 1;
dp[x / SQ] = false;
a[x] = false;
}
else if (a[x]) {
a[x] = false;
sum[x / SQ]--;
}
}
int ask(int x) {
int res = 0;
for (int i = 0; (i + 1) * SQ - 1 < x; i++)
res += sum[i];
if (dp[x / SQ])
res += (x % SQ) + 1;
else
for (int i = x - x % SQ; i <= x; i++)
res += a[i];
return res;
}
void query() {
while (q--) {
int u, v;
cin >> u >> v;
if (u == 1) {
int l = -1, r = n;
while (r - l > 1) {
int mid = (l + r) / 2;
if (mid + 1 - ask(mid) <= v)
l = mid;
else
r = mid;
}
cout << f[l] + 1 << '\n';
add(l + 1);
}
else {
v--;
int z = v;
for (int i = M - 1; ~i; i--)
if ((ask(p[par[i][v]]) - ask(p[par[i][v]] - 1)) > 0)
v = par[i][v];
cout << h[z] - h[v] << '\n';
rem(p[v]);
}
}
}
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
ip(), pre(), query();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
21336 KB |
Output isn't correct |
| 2 |
Incorrect |
882 ms |
24812 KB |
Output isn't correct |
| 3 |
Incorrect |
484 ms |
24892 KB |
Output isn't correct |
| 4 |
Incorrect |
3 ms |
21336 KB |
Output isn't correct |
| 5 |
Incorrect |
4 ms |
21340 KB |
Output isn't correct |
| 6 |
Incorrect |
5 ms |
21336 KB |
Output isn't correct |
| 7 |
Incorrect |
5 ms |
21596 KB |
Output isn't correct |
| 8 |
Incorrect |
5 ms |
21340 KB |
Output isn't correct |
| 9 |
Incorrect |
42 ms |
21756 KB |
Output isn't correct |
| 10 |
Incorrect |
62 ms |
22356 KB |
Output isn't correct |
| 11 |
Incorrect |
900 ms |
24724 KB |
Output isn't correct |
| 12 |
Incorrect |
480 ms |
24912 KB |
Output isn't correct |
| 13 |
Incorrect |
806 ms |
24488 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
25168 KB |
Output isn't correct |
| 2 |
Incorrect |
674 ms |
33180 KB |
Output isn't correct |
| 3 |
Incorrect |
511 ms |
25820 KB |
Output isn't correct |
| 4 |
Incorrect |
444 ms |
25248 KB |
Output isn't correct |
| 5 |
Incorrect |
358 ms |
25128 KB |
Output isn't correct |
| 6 |
Incorrect |
384 ms |
25168 KB |
Output isn't correct |
| 7 |
Incorrect |
345 ms |
23644 KB |
Output isn't correct |
| 8 |
Incorrect |
131 ms |
25424 KB |
Output isn't correct |
| 9 |
Incorrect |
752 ms |
32340 KB |
Output isn't correct |
| 10 |
Incorrect |
695 ms |
33132 KB |
Output isn't correct |
| 11 |
Incorrect |
534 ms |
33160 KB |
Output isn't correct |
| 12 |
Incorrect |
658 ms |
29000 KB |
Output isn't correct |
| 13 |
Incorrect |
392 ms |
37300 KB |
Output isn't correct |
| 14 |
Incorrect |
507 ms |
25656 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
260 ms |
26964 KB |
Output is correct |
| 2 |
Incorrect |
807 ms |
29484 KB |
Output isn't correct |
| 3 |
Incorrect |
363 ms |
35696 KB |
Output isn't correct |
| 4 |
Correct |
445 ms |
30232 KB |
Output is correct |
| 5 |
Incorrect |
398 ms |
30864 KB |
Output isn't correct |
| 6 |
Incorrect |
417 ms |
30804 KB |
Output isn't correct |
| 7 |
Correct |
433 ms |
27696 KB |
Output is correct |
| 8 |
Incorrect |
379 ms |
35776 KB |
Output isn't correct |
| 9 |
Correct |
854 ms |
32892 KB |
Output is correct |
| 10 |
Incorrect |
820 ms |
33376 KB |
Output isn't correct |
| 11 |
Correct |
766 ms |
33152 KB |
Output is correct |
| 12 |
Incorrect |
791 ms |
29500 KB |
Output isn't correct |
| 13 |
Incorrect |
740 ms |
39312 KB |
Output isn't correct |
| 14 |
Execution timed out |
1022 ms |
25916 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
697 ms |
32560 KB |
Output isn't correct |
| 2 |
Incorrect |
739 ms |
29460 KB |
Output isn't correct |
| 3 |
Incorrect |
392 ms |
39272 KB |
Output isn't correct |
| 4 |
Incorrect |
697 ms |
32592 KB |
Output isn't correct |
| 5 |
Incorrect |
676 ms |
33108 KB |
Output isn't correct |
| 6 |
Incorrect |
540 ms |
33108 KB |
Output isn't correct |
| 7 |
Incorrect |
741 ms |
29512 KB |
Output isn't correct |
| 8 |
Incorrect |
439 ms |
39496 KB |
Output isn't correct |
| 9 |
Incorrect |
556 ms |
25700 KB |
Output isn't correct |
