#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 (T[i].size() && 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 |
29 ms |
24192 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
141 ms |
47608 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Incorrect |
160 ms |
24360 KB |
Output isn't correct |
| 4 |
Execution timed out |
1070 ms |
12132 KB |
Time limit exceeded |
| 5 |
Runtime error |
29 ms |
24192 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 |
1061 ms |
12288 KB |
Time limit exceeded |
| 8 |
Runtime error |
29 ms |
24448 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 |
49 ms |
29944 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
184 ms |
47608 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Incorrect |
205 ms |
24412 KB |
Output isn't correct |
| 13 |
Execution timed out |
1072 ms |
24056 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
238 ms |
26572 KB |
Output isn't correct |
| 2 |
Runtime error |
666 ms |
123640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Incorrect |
197 ms |
26972 KB |
Output isn't correct |
| 4 |
Runtime error |
231 ms |
51992 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
170 ms |
51108 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
170 ms |
51248 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
166 ms |
47236 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Incorrect |
200 ms |
26504 KB |
Output isn't correct |
| 9 |
Runtime error |
891 ms |
109404 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
741 ms |
123544 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
663 ms |
123384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
681 ms |
115192 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Execution timed out |
1073 ms |
90348 KB |
Time limit exceeded |
| 14 |
Incorrect |
175 ms |
27060 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
327 ms |
69536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
814 ms |
115904 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Execution timed out |
1082 ms |
72184 KB |
Time limit exceeded |
| 4 |
Runtime error |
631 ms |
98680 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
607 ms |
102884 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
573 ms |
103032 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
547 ms |
96444 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Execution timed out |
1077 ms |
72632 KB |
Time limit exceeded |
| 9 |
Runtime error |
746 ms |
120436 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
942 ms |
123296 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
814 ms |
123756 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
870 ms |
116124 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Execution timed out |
1083 ms |
83204 KB |
Time limit exceeded |
| 14 |
Runtime error |
204 ms |
53092 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
689 ms |
129228 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
676 ms |
115844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Execution timed out |
1075 ms |
84956 KB |
Time limit exceeded |
| 4 |
Runtime error |
728 ms |
129284 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
716 ms |
123256 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Execution timed out |
1050 ms |
62452 KB |
Time limit exceeded |
| 7 |
Runtime error |
820 ms |
115832 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Execution timed out |
1074 ms |
86672 KB |
Time limit exceeded |
| 9 |
Correct |
163 ms |
26788 KB |
Output is correct |
