#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, q, ts, P[N], H[N], rev[N], st[N], fn[N], mn[N];
vector < int > Adj[N];
set < int > S;
struct CMPH {
inline bool operator () (int v, int u) {
return (H[v] > H[u]);
}
};
set < int , CMPH > T[N * 2];
bool CMP(int i, int j)
{
return (mn[i] < mn[j]);
}
bool CMP2(int i, int j)
{
return (st[i] < st[j]);
}
void DFS(int v)
{
mn[v] = v;
st[v] = ts ++;
for (int &u : Adj[v])
{
H[u] = H[v] + 1;
DFS(u);
mn[v] = min(mn[v], mn[u]);
}
fn[v] = ts;
}
void DFS2(int v)
{
for (int &u : Adj[v])
DFS2(u);
P[v] = ts ++;
rev[P[v]] = v;
S.insert(P[v]);
}
inline void Add(int le, int ri, int v)
{
le += n + 1;
ri += n + 1;
for (; le < ri; le >>= 1, ri >>= 1)
{
if (le & 1) T[le].insert(v), le ++;
if (ri & 1) ri --, T[ri].insert(v);
}
}
inline void Del(int le, int ri, int v)
{
le += n + 1;
ri += n + 1;
for (; le < ri; le >>= 1, ri >>= 1)
{
if (le & 1) T[le].erase(v), le ++;
if (ri & 1) ri --, T[ri].erase(v);
}
}
inline int Get(int i)
{
int v = 0;
i += n + 1;
for (; i; i >>= 1)
if (H[v] < H[*T[i].begin()])
v = *T[i].begin();
return (v);
}
int main()
{
scanf("%d%d", &n, &q);
for (int i = 1, p; i <= n; i++)
scanf("%d", &p), Adj[p].push_back(i);
DFS(0);
for (int i = 0; i <= n; i++)
sort(Adj[i].begin(), Adj[i].end(), CMP);
ts = 0; DFS2(0);
for (int i = 0; i <= n; i++)
Add(st[i], fn[i], i);
for (int i = 0; i <= n; i++)
sort(Adj[i].begin(), Adj[i].end(), CMP2);
for (; q; q --)
{
int tp, v;
scanf("%d%d", &tp, &v);
if (tp == 1)
{
int u;
for (; v; v --)
{
u = rev[*S.begin()];
S.erase(S.begin());
Del(st[u], fn[u], u);
}
printf("%d\n", u);
}
else
{
int u = Get(st[v]);
int lb = upper_bound(Adj[u].begin(), Adj[u].end(), st[v], CMP2) - Adj[u].begin() - 1;
u = Adj[u][lb];
S.insert(P[u]);
Add(st[u], fn[u], u);
printf("%d\n", H[v] - H[u]);
}
}
return 0;
}
Compilation message
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:72: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:74:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &p), Adj[p].push_back(i);
~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &tp, &v);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
28 ms |
24192 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
165 ms |
48268 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Incorrect |
179 ms |
25336 KB |
Output isn't correct |
| 4 |
Execution timed out |
1074 ms |
12076 KB |
Time limit exceeded |
| 5 |
Runtime error |
24 ms |
24064 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Incorrect |
15 ms |
12288 KB |
Output isn't correct |
| 7 |
Execution timed out |
1047 ms |
12288 KB |
Time limit exceeded |
| 8 |
Runtime error |
30 ms |
24440 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
42 ms |
25464 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
60 ms |
30136 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
145 ms |
48144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Incorrect |
182 ms |
25280 KB |
Output isn't correct |
| 13 |
Execution timed out |
1052 ms |
25120 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
253 ms |
27028 KB |
Output isn't correct |
| 2 |
Runtime error |
711 ms |
124132 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Incorrect |
200 ms |
28020 KB |
Output isn't correct |
| 4 |
Runtime error |
226 ms |
52436 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
187 ms |
51448 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
162 ms |
51728 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
142 ms |
47608 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Incorrect |
208 ms |
27004 KB |
Output isn't correct |
| 9 |
Runtime error |
935 ms |
110428 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
655 ms |
124152 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
774 ms |
124324 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
588 ms |
115852 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Execution timed out |
1044 ms |
87172 KB |
Time limit exceeded |
| 14 |
Incorrect |
153 ms |
28020 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
320 ms |
69892 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
762 ms |
116600 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Execution timed out |
1068 ms |
73012 KB |
Time limit exceeded |
| 4 |
Runtime error |
654 ms |
99324 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
552 ms |
103416 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
696 ms |
103804 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
614 ms |
97072 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Execution timed out |
1059 ms |
72648 KB |
Time limit exceeded |
| 9 |
Runtime error |
977 ms |
121272 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
950 ms |
124096 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Execution timed out |
1059 ms |
124132 KB |
Time limit exceeded |
| 12 |
Runtime error |
720 ms |
116828 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Execution timed out |
1077 ms |
84028 KB |
Time limit exceeded |
| 14 |
Runtime error |
214 ms |
53820 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
825 ms |
130144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
800 ms |
116604 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Execution timed out |
1077 ms |
84556 KB |
Time limit exceeded |
| 4 |
Runtime error |
722 ms |
130172 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
757 ms |
124152 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Incorrect |
995 ms |
63696 KB |
Output isn't correct |
| 7 |
Runtime error |
711 ms |
116632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Execution timed out |
1071 ms |
83688 KB |
Time limit exceeded |
| 9 |
Correct |
217 ms |
27764 KB |
Output is correct |
