#include <bits/stdc++.h>
using namespace std;
#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
const int MXN = 100005, LG = 18;
int n, q, rt;
vector<pii> chd[MXN];
int d[MXN], dfn[MXN], scr[MXN], sml[MXN], C;
int p[LG][MXN];
bitset<MXN> b;
priority_queue<int, vector<int>, greater<int>> pq;
void DFS(int id, int par, int dep) {
p[0][id] = par;
d[id] = dep;
sml[id] = id;
for (auto &[e, i] : chd[id]) {
DFS(i, id, dep + 1);
sml[id] = min(sml[id], sml[i]);
}
}
void DFS2(int id) {
for (auto &[e, i] : chd[id]) e = sml[i];
sort(chd[id].begin(), chd[id].end());
for (auto &[e, i] : chd[id]) DFS2(i);
scr[C] = id;
dfn[id] = C++;
}
int calc1(int x) {
int ans = 0;
while (x--) {
int id = pq.top();
pq.pop();
b[scr[id]] = true;
ans = scr[id];
}
return ans;
}
int calc2(int x) {
int x0 = x;
for (int w = LG - 1; w >= 0; w--) {
if (!b[p[w][x]]) continue;
x = p[w][x];
}
b[x] = false;
pq.push(dfn[x]);
return d[x0] - d[x];
}
void miku() {
int x, y;
cin >> n >> q;
FOR(i, 1, n + 1) {
cin >> x;
if (x == 0) rt = i;
else chd[x].push_back(mp(0, i));
}
DFS(rt, 0, 0);
DFS2(rt);
FOR(w, 1, LG) {
FOR(i, 1, n + 1) p[w][i] = p[w - 1][p[w - 1][i]];
}
FOR(i, 0, n) pq.push(i);
while (q--) {
cin >> x >> y;
if (x == 1) cout << calc1(y) << '\n';
else cout << calc2(y) << '\n';
}
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
cin.exceptions(cin.failbit);
miku();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
11236 KB |
Output is correct |
2 |
Correct |
74 ms |
14032 KB |
Output is correct |
3 |
Correct |
44 ms |
13920 KB |
Output is correct |
4 |
Correct |
2 ms |
11100 KB |
Output is correct |
5 |
Correct |
4 ms |
11260 KB |
Output is correct |
6 |
Correct |
2 ms |
11096 KB |
Output is correct |
7 |
Correct |
3 ms |
11096 KB |
Output is correct |
8 |
Correct |
3 ms |
11100 KB |
Output is correct |
9 |
Correct |
8 ms |
11356 KB |
Output is correct |
10 |
Correct |
15 ms |
11864 KB |
Output is correct |
11 |
Correct |
94 ms |
13892 KB |
Output is correct |
12 |
Correct |
36 ms |
13680 KB |
Output is correct |
13 |
Correct |
78 ms |
13776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
13856 KB |
Output is correct |
2 |
Correct |
88 ms |
18232 KB |
Output is correct |
3 |
Correct |
56 ms |
14408 KB |
Output is correct |
4 |
Correct |
58 ms |
13960 KB |
Output is correct |
5 |
Correct |
54 ms |
13644 KB |
Output is correct |
6 |
Correct |
51 ms |
14052 KB |
Output is correct |
7 |
Correct |
52 ms |
13492 KB |
Output is correct |
8 |
Correct |
23 ms |
13916 KB |
Output is correct |
9 |
Correct |
87 ms |
18840 KB |
Output is correct |
10 |
Correct |
89 ms |
18376 KB |
Output is correct |
11 |
Correct |
86 ms |
18368 KB |
Output is correct |
12 |
Correct |
103 ms |
16736 KB |
Output is correct |
13 |
Correct |
55 ms |
21200 KB |
Output is correct |
14 |
Correct |
40 ms |
14392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
15356 KB |
Output is correct |
2 |
Correct |
83 ms |
16900 KB |
Output is correct |
3 |
Correct |
75 ms |
20484 KB |
Output is correct |
4 |
Correct |
61 ms |
17068 KB |
Output is correct |
5 |
Correct |
66 ms |
16664 KB |
Output is correct |
6 |
Correct |
60 ms |
16840 KB |
Output is correct |
7 |
Correct |
58 ms |
15644 KB |
Output is correct |
8 |
Correct |
76 ms |
20236 KB |
Output is correct |
9 |
Correct |
110 ms |
18900 KB |
Output is correct |
10 |
Correct |
101 ms |
18380 KB |
Output is correct |
11 |
Correct |
91 ms |
18372 KB |
Output is correct |
12 |
Correct |
116 ms |
16872 KB |
Output is correct |
13 |
Correct |
88 ms |
22920 KB |
Output is correct |
14 |
Correct |
89 ms |
14612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
97 ms |
18924 KB |
Output is correct |
2 |
Correct |
104 ms |
16820 KB |
Output is correct |
3 |
Correct |
57 ms |
22620 KB |
Output is correct |
4 |
Correct |
113 ms |
18900 KB |
Output is correct |
5 |
Correct |
93 ms |
18520 KB |
Output is correct |
6 |
Correct |
92 ms |
18560 KB |
Output is correct |
7 |
Correct |
91 ms |
16964 KB |
Output is correct |
8 |
Correct |
53 ms |
22560 KB |
Output is correct |
9 |
Correct |
39 ms |
14416 KB |
Output is correct |