#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <complex>
#include <stack>
#include <set>
#include <fstream>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<ll,ll>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double>
const ll INF = 4e18;
using namespace std;
const int MAXN = 100005;
vi g[MAXN];
int sparseTable[20][MAXN];
int DPmin[MAXN];
int dpt[MAXN];
int parent[MAXN];
set<ii> s;
int status[MAXN];
void dfs1(int node,int p){
dpt[node] = ((p!=-1)?dpt[p]+1:0);
parent[node] = p;
vector<ii> all;
DPmin[node] = node;
for(auto e:g[node]){
if(e==p)continue;
dfs1(e,node);
all.pb({DPmin[e],e});
DPmin[node] = min(DPmin[node],DPmin[e]);
}
sort(all.begin(), all.end());
g[node].clear();
for(auto e:all)g[node].pb(e.ss);
g[node].pb(p);
}
int T = 0;
int __tm__[MAXN];
void dfs2(int node,int p){
for(auto e:g[node]){
if(e!=p)dfs2(e,node);
}
__tm__[node] = T;
s.insert({T++,node});
}
void buildSparseTable(int n){
FOR(i,n)sparseTable[0][i] = parent[i];
FORE(i,1,19){
FOR(node,n){
int p = sparseTable[i-1][node];
if(p == -1){
sparseTable[i][node] = -1;
}else{
sparseTable[i][node] = sparseTable[i-1][p];
}
}
}
}
inline int findFirstAncestor(int n,int a){
int k = 20;
while(k--){
int p = sparseTable[k][a];
if(p == -1 or status[p] == 0){
}else{
a=p;
}
}
return a;
}
int main(){
int n,q;
cin >> n >> q;
FOR(i,n){
int a;
cin >> a;
a--;
if(a >= 0)g[a].pb(i);
}
dfs1(0,-1);
dfs2(0,-1);
buildSparseTable(n);
while(q--){
int t,a;
cin >> t >> a;
if(t == 1){
int last = 0;
FOR(i,a){
ii to = *s.begin();
s.erase(to);
status[to.ss] = 1;
last = to.ss+1;
}
cout << last << endl;
}else{
a--;
int p = findFirstAncestor(n,a);
s.insert({__tm__[p],p});
status[p] = 0;
cout << dpt[a]-dpt[p] << endl;
}
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
7 ms |
2944 KB |
Output isn't correct |
2 |
Incorrect |
367 ms |
12044 KB |
Output isn't correct |
3 |
Correct |
217 ms |
10560 KB |
Output is correct |
4 |
Incorrect |
4 ms |
2816 KB |
Output isn't correct |
5 |
Incorrect |
4 ms |
2816 KB |
Output isn't correct |
6 |
Incorrect |
5 ms |
2944 KB |
Output isn't correct |
7 |
Incorrect |
6 ms |
2944 KB |
Output isn't correct |
8 |
Incorrect |
8 ms |
2944 KB |
Output isn't correct |
9 |
Incorrect |
26 ms |
3448 KB |
Output isn't correct |
10 |
Incorrect |
68 ms |
5288 KB |
Output isn't correct |
11 |
Incorrect |
364 ms |
12896 KB |
Output isn't correct |
12 |
Correct |
226 ms |
10360 KB |
Output is correct |
13 |
Incorrect |
276 ms |
10640 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
205 ms |
9720 KB |
Output is correct |
2 |
Incorrect |
609 ms |
23288 KB |
Output isn't correct |
3 |
Correct |
256 ms |
13144 KB |
Output is correct |
4 |
Incorrect |
247 ms |
8676 KB |
Output isn't correct |
5 |
Incorrect |
266 ms |
8588 KB |
Output isn't correct |
6 |
Incorrect |
206 ms |
6976 KB |
Output isn't correct |
7 |
Incorrect |
230 ms |
7800 KB |
Output isn't correct |
8 |
Correct |
170 ms |
9720 KB |
Output is correct |
9 |
Incorrect |
630 ms |
28620 KB |
Output isn't correct |
10 |
Incorrect |
604 ms |
23164 KB |
Output isn't correct |
11 |
Incorrect |
341 ms |
14628 KB |
Output isn't correct |
12 |
Incorrect |
420 ms |
17272 KB |
Output isn't correct |
13 |
Correct |
285 ms |
20472 KB |
Output is correct |
14 |
Correct |
296 ms |
13160 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
284 ms |
15408 KB |
Output isn't correct |
2 |
Incorrect |
619 ms |
24056 KB |
Output isn't correct |
3 |
Incorrect |
360 ms |
19836 KB |
Output isn't correct |
4 |
Incorrect |
242 ms |
14432 KB |
Output isn't correct |
5 |
Incorrect |
245 ms |
14340 KB |
Output isn't correct |
6 |
Incorrect |
227 ms |
14388 KB |
Output isn't correct |
7 |
Incorrect |
313 ms |
19448 KB |
Output isn't correct |
8 |
Incorrect |
319 ms |
19960 KB |
Output isn't correct |
9 |
Incorrect |
458 ms |
18656 KB |
Output isn't correct |
10 |
Incorrect |
427 ms |
18424 KB |
Output isn't correct |
11 |
Incorrect |
492 ms |
21752 KB |
Output isn't correct |
12 |
Incorrect |
531 ms |
24172 KB |
Output isn't correct |
13 |
Incorrect |
512 ms |
23660 KB |
Output isn't correct |
14 |
Incorrect |
423 ms |
18852 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
390 ms |
16740 KB |
Output isn't correct |
2 |
Incorrect |
677 ms |
24596 KB |
Output isn't correct |
3 |
Correct |
481 ms |
33916 KB |
Output is correct |
4 |
Incorrect |
418 ms |
16836 KB |
Output isn't correct |
5 |
Incorrect |
379 ms |
16248 KB |
Output isn't correct |
6 |
Correct |
521 ms |
28436 KB |
Output is correct |
7 |
Incorrect |
609 ms |
24584 KB |
Output isn't correct |
8 |
Correct |
345 ms |
33788 KB |
Output is correct |
9 |
Correct |
241 ms |
13044 KB |
Output is correct |