#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<int> edge[MXN];
vector<int> chd[MXN];
int d[MXN], dfn[MXN], scr[MXN], C;
int p[LG][MXN];
bitset<MXN> b;
set<int> S;
void DFS(int id, int par, int dep) {
p[0][id] = par;
d[id] = dep;
for (auto &i : edge[id]) {
if (i == par) continue;
chd[id].push_back(i);
}
sort(chd[id].begin(), chd[id].end());
for (auto &i : chd[id]) {
DFS(i, id, dep + 1);
}
scr[C] = id;
dfn[id] = C++;
}
int calc1(int x) {
int ans = 0;
while (x--) {
int id = *S.begin();
S.erase(S.begin());
b[scr[id]] = true;
ans = scr[id];
debug(ans);
}
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;
S.insert(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 {
edge[i].push_back(x);
edge[x].push_back(i);
}
}
DFS(rt, rt, 0);
// FOR(i, 0, n) cout << scr[i] << ' ';
// cout << endl;
FOR(w, 1, LG) {
FOR(i, 1, n + 1) p[w][i] = p[w - 1][p[w - 1][i]];
}
FOR(i, 0, n) S.insert(i);
while (q--) {
cin >> x >> y;
if (x == 1) cout << calc1(y) << '\n';
else cout << calc2(y) << '\n';
// for (auto i : S) cout << i << ' ';
// cout << endl;
}
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
cin.exceptions(cin.failbit);
miku();
return 0;
}
Compilation message
ballmachine.cpp: In function 'int calc1(int)':
ballmachine.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
ballmachine.cpp:52:9: note: in expansion of macro 'debug'
52 | debug(ans);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
13148 KB |
Output isn't correct |
| 2 |
Execution timed out |
1074 ms |
19536 KB |
Time limit exceeded |
| 3 |
Incorrect |
62 ms |
19792 KB |
Output isn't correct |
| 4 |
Execution timed out |
1052 ms |
13144 KB |
Time limit exceeded |
| 5 |
Incorrect |
3 ms |
13148 KB |
Output isn't correct |
| 6 |
Incorrect |
3 ms |
13148 KB |
Output isn't correct |
| 7 |
Execution timed out |
1053 ms |
13144 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1060 ms |
13148 KB |
Time limit exceeded |
| 9 |
Incorrect |
10 ms |
13404 KB |
Output isn't correct |
| 10 |
Execution timed out |
1075 ms |
14684 KB |
Time limit exceeded |
| 11 |
Incorrect |
183 ms |
19688 KB |
Output isn't correct |
| 12 |
Incorrect |
56 ms |
19852 KB |
Output isn't correct |
| 13 |
Incorrect |
103 ms |
19608 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
16948 KB |
Output is correct |
| 2 |
Incorrect |
184 ms |
27316 KB |
Output isn't correct |
| 3 |
Incorrect |
65 ms |
22972 KB |
Output isn't correct |
| 4 |
Execution timed out |
1083 ms |
17500 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1091 ms |
17204 KB |
Time limit exceeded |
| 6 |
Incorrect |
71 ms |
17568 KB |
Output isn't correct |
| 7 |
Incorrect |
71 ms |
16580 KB |
Output isn't correct |
| 8 |
Correct |
33 ms |
16928 KB |
Output is correct |
| 9 |
Incorrect |
196 ms |
27612 KB |
Output isn't correct |
| 10 |
Incorrect |
169 ms |
27392 KB |
Output isn't correct |
| 11 |
Incorrect |
134 ms |
27220 KB |
Output isn't correct |
| 12 |
Incorrect |
208 ms |
25024 KB |
Output isn't correct |
| 13 |
Correct |
76 ms |
30156 KB |
Output is correct |
| 14 |
Incorrect |
73 ms |
23052 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
20428 KB |
Output isn't correct |
| 2 |
Incorrect |
250 ms |
25436 KB |
Output isn't correct |
| 3 |
Correct |
89 ms |
28576 KB |
Output is correct |
| 4 |
Incorrect |
103 ms |
24796 KB |
Output isn't correct |
| 5 |
Incorrect |
115 ms |
24484 KB |
Output isn't correct |
| 6 |
Incorrect |
139 ms |
24500 KB |
Output isn't correct |
| 7 |
Incorrect |
105 ms |
22900 KB |
Output isn't correct |
| 8 |
Correct |
109 ms |
28520 KB |
Output is correct |
| 9 |
Incorrect |
226 ms |
27868 KB |
Output isn't correct |
| 10 |
Incorrect |
180 ms |
27352 KB |
Output isn't correct |
| 11 |
Incorrect |
217 ms |
27288 KB |
Output isn't correct |
| 12 |
Incorrect |
240 ms |
25488 KB |
Output isn't correct |
| 13 |
Correct |
172 ms |
32544 KB |
Output is correct |
| 14 |
Incorrect |
210 ms |
22860 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
204 ms |
27868 KB |
Output isn't correct |
| 2 |
Incorrect |
180 ms |
25388 KB |
Output isn't correct |
| 3 |
Correct |
99 ms |
32464 KB |
Output is correct |
| 4 |
Incorrect |
188 ms |
27784 KB |
Output isn't correct |
| 5 |
Incorrect |
171 ms |
27224 KB |
Output isn't correct |
| 6 |
Incorrect |
137 ms |
27336 KB |
Output isn't correct |
| 7 |
Incorrect |
197 ms |
25372 KB |
Output isn't correct |
| 8 |
Correct |
104 ms |
32296 KB |
Output is correct |
| 9 |
Incorrect |
74 ms |
23000 KB |
Output isn't correct |
