#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
#ifdef MY_DEBUG_FLAG
template<typename T> void debug(T a) { cerr << a << ' '; }
template<typename T, typename U> void debug(pair<T, U> a) { cerr << a.first << ' ' << a.second << ' '; }
template<typename T> void debug(vector<T> a) { for(auto it : a) debug(it);}
template<typename T> void debug(set<T> a) { for(auto it : a) debug(it);}
#define db(a) cerr << "DEBUG ( " << #a << " == "; debug(a); cerr << ")\n"
#else
#define db(...)
#endif
#define pb push_back
#define ff first
#define ss second
#define fast ios_base::sync_with_stdio(false), cout.tie(nullptr), cin.tie(nullptr)
#define sz(a) ((int)(a).size())
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define dec(i,n,a) for(int i=(n); i>=(a); i--)
#define clr(a,v) memset(a, v, sizeof(a))
#define all(a) (a).begin(),(a).end()
constexpr int inf = 0x3f3f3f3f;
constexpr int MAXN = 1e5 + 10;
constexpr int LOGN = 20;
constexpr int mod = 1000000007;
int n, root;
int pai[MAXN][LOGN], menor[MAXN], in[MAXN], out[MAXN], aux = 0;
bool act[MAXN];
vi g[MAXN]; // contains only the children of a node
int calc_menor(int u) {
int ans = u;
for(auto v : g[u]) {
ans = min(ans, calc_menor(v));
}
return ans;
}
void dfs(int u) {
in[u] = aux++;
sort(all(g[u]), [](const int& a, const int& b) {
return menor[a] < menor[b];
});
for(auto v : g[u]) {
dfs(v);
}
out[u] = aux++;
}
struct comp {
bool operator()(const int& a, const int& b) {
return in[a] < in[b];
}
};
priority_queue<int, vector<int>, comp> q;
void binary_parents() {
for(int j = 1; j < LOGN; j++) {
for(int i = 1; i <= n; i++) {
if(pai[i][j-1] == 0) continue;
pai[i][j] = pai[pai[i][j-1]][j-1];
}
}
}
int bit[2*MAXN];
void upd(int x, int v) {
for(x++; x < MAXN; x += x&-x)
bit[x] += v;
}
int query(int x) {
int ans = 0;
for(x++; x > 0; x -= x&-x)
ans += bit[x];
return ans;
}
int add() {
assert(!q.empty());
int now = q.top(); // db(now);
q.pop();
act[now] = 1;
upd(in[now], 1);
upd(out[now], -1);
return now;
}
void remove(int k) {
// db(act[k]);
dec(i,LOGN,0) {
if(act[pai[k][i]]) k = pai[k][i];
}
assert(act[k]);
act[k] = 0;
q.push(k);
upd(in[k], -1); upd(out[k], 1);
}
int main() {
int Q;
scanf("%d %d", &n, &Q);
rep(i,1,n+1) {
int p; scanf("%d", &p);
pai[i][0] = p;
if(p == 0) root = i;
else g[p].pb(i);
}
binary_parents();
calc_menor(root);
dfs(root);
// int oi, cnta = 0;
// while(1) { cin >> oi; db(oi); db(cnta++); }
rep(i,1,n+1) q.push(i);
while(Q--) {
int type, k;
scanf("%d %d", &type, &k);
if(type == 1) {
rep(i,0,k) {
if(i == k-1) printf("%d\n", add());
else add(); // returns the position that was added
}
}
else {
printf("%d\n", query(in[k]-1)); // how many active parents he has
remove(k); // removes the last parent of this guy
}
}
// rep(i,1,n+1) { db(i), db(act[i]); }
}
Compilation message
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:113:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &Q);
~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp:115:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int p; scanf("%d", &p);
~~~~~^~~~~~~~~~
ballmachine.cpp:132:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &type, &k);
~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
5504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
49 ms |
20472 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
43 ms |
20216 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
9 ms |
5376 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
10 ms |
5376 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
10 ms |
5632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
10 ms |
5632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
10 ms |
5632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
12 ms |
6272 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
21 ms |
9344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
53 ms |
20600 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
45 ms |
20472 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
50 ms |
20240 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
7032 KB |
Output is correct |
| 2 |
Runtime error |
98 ms |
34932 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
60 ms |
27504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
32 ms |
15104 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
29 ms |
14712 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
27 ms |
14584 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
28 ms |
13312 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Correct |
56 ms |
7032 KB |
Output is correct |
| 9 |
Runtime error |
95 ms |
35812 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
92 ms |
34928 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
98 ms |
34976 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
82 ms |
31216 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Correct |
112 ms |
20592 KB |
Output is correct |
| 14 |
Runtime error |
59 ms |
27500 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
59 ms |
21620 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
121 ms |
33012 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Correct |
137 ms |
19184 KB |
Output is correct |
| 4 |
Runtime error |
84 ms |
30320 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
80 ms |
29684 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
83 ms |
29684 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
80 ms |
27240 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Correct |
138 ms |
19188 KB |
Output is correct |
| 9 |
Runtime error |
115 ms |
36720 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
120 ms |
35824 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
128 ms |
35956 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
121 ms |
32756 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Correct |
215 ms |
23540 KB |
Output is correct |
| 14 |
Runtime error |
83 ms |
28528 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
96 ms |
35824 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
101 ms |
32240 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Correct |
120 ms |
22768 KB |
Output is correct |
| 4 |
Runtime error |
90 ms |
35820 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
101 ms |
35316 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
88 ms |
34928 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
118 ms |
32240 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Correct |
132 ms |
22772 KB |
Output is correct |
| 9 |
Runtime error |
61 ms |
27504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
