#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n = 1e5 + 5,root = -1,q;
int timer = 0;
vvi adj(n),dp(n,vi(21));
vi out(n),minNode(n),dep(n);
vb is(n);
set<pair<int,int>>unfilled;
bool cmp(int u,int v)
{
return minNode[u] < minNode[v];
}
int compute(int u,int p)
{
minNode[u] = u;
for (int v:adj[u])if (v != p)minNode[u] = min(minNode[u],compute(v,u));
return minNode[u];
}
void dfs(int u,int p)
{
dep[u] = dep[p] + 1;
dp[u][0] = p;
for (int i = 1;i<=20;i++)dp[u][i] = dp[dp[u][i - 1]][i - 1];
sort(adj[u].begin(),adj[u].end(),cmp);
for (int v:adj[u]){
if (v == p)continue;
dfs(v,u);
}
out[u] = ++timer;
unfilled.insert({out[u],u});
}
int add()
{
auto it = unfilled.begin();
unfilled.erase(it);
is[(*it).second] = 1;
return (*it).second;
}
int sub(int u)
{
int v = u;
for (int i = 20;i>=0;i--){
if (is[dp[v][i]])v = dp[v][i];
}
is[v] = 0;
unfilled.insert({out[v],v});
return dep[u] - dep[v];
}
int main()
{
fast;
cin>>n>>q;
for (int i = 0;i<n;i++){
int p;
cin>>p;
p--;
if (p == -1)root = i;
else adj[p].pb(i);
}
compute(root,root);
dfs(root,root);
while (q--){
int t,u;
cin>>t>>u;
if (t == 1){
while (u-- > 1)add();
cout<<add() + 1<<'\n';
}
else{
cout<<sub(u - 1)<<'\n';
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
15596 KB |
Output is correct |
2 |
Correct |
198 ms |
21100 KB |
Output is correct |
3 |
Correct |
109 ms |
21100 KB |
Output is correct |
4 |
Correct |
15 ms |
15596 KB |
Output is correct |
5 |
Correct |
15 ms |
15596 KB |
Output is correct |
6 |
Correct |
19 ms |
15724 KB |
Output is correct |
7 |
Correct |
16 ms |
15744 KB |
Output is correct |
8 |
Correct |
17 ms |
15724 KB |
Output is correct |
9 |
Correct |
23 ms |
15980 KB |
Output is correct |
10 |
Correct |
40 ms |
16876 KB |
Output is correct |
11 |
Correct |
194 ms |
21040 KB |
Output is correct |
12 |
Correct |
110 ms |
21100 KB |
Output is correct |
13 |
Correct |
151 ms |
21100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
19672 KB |
Output is correct |
2 |
Correct |
293 ms |
28544 KB |
Output is correct |
3 |
Correct |
133 ms |
22888 KB |
Output is correct |
4 |
Correct |
108 ms |
20076 KB |
Output is correct |
5 |
Correct |
110 ms |
19948 KB |
Output is correct |
6 |
Correct |
103 ms |
19948 KB |
Output is correct |
7 |
Correct |
112 ms |
19052 KB |
Output is correct |
8 |
Correct |
62 ms |
19564 KB |
Output is correct |
9 |
Correct |
248 ms |
28908 KB |
Output is correct |
10 |
Correct |
294 ms |
28524 KB |
Output is correct |
11 |
Correct |
254 ms |
28524 KB |
Output is correct |
12 |
Correct |
272 ms |
25964 KB |
Output is correct |
13 |
Correct |
215 ms |
32364 KB |
Output is correct |
14 |
Correct |
130 ms |
22888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
127 ms |
22340 KB |
Output is correct |
2 |
Correct |
332 ms |
26348 KB |
Output is correct |
3 |
Correct |
232 ms |
30700 KB |
Output is correct |
4 |
Correct |
211 ms |
26220 KB |
Output is correct |
5 |
Correct |
214 ms |
25836 KB |
Output is correct |
6 |
Correct |
232 ms |
26020 KB |
Output is correct |
7 |
Correct |
207 ms |
23916 KB |
Output is correct |
8 |
Correct |
229 ms |
30700 KB |
Output is correct |
9 |
Correct |
303 ms |
29164 KB |
Output is correct |
10 |
Correct |
336 ms |
28708 KB |
Output is correct |
11 |
Correct |
338 ms |
28652 KB |
Output is correct |
12 |
Correct |
339 ms |
26348 KB |
Output is correct |
13 |
Correct |
353 ms |
34796 KB |
Output is correct |
14 |
Correct |
228 ms |
23272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
294 ms |
29292 KB |
Output is correct |
2 |
Correct |
316 ms |
26428 KB |
Output is correct |
3 |
Correct |
241 ms |
34412 KB |
Output is correct |
4 |
Correct |
287 ms |
29164 KB |
Output is correct |
5 |
Correct |
318 ms |
28652 KB |
Output is correct |
6 |
Correct |
268 ms |
28652 KB |
Output is correct |
7 |
Correct |
316 ms |
26348 KB |
Output is correct |
8 |
Correct |
254 ms |
34412 KB |
Output is correct |
9 |
Correct |
129 ms |
22888 KB |
Output is correct |