#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 1e5 + 10, LOG = 18;
bool full[N];
vector<int> adj[N];
int n, root, g[N], mn[N], par[N][LOG], ord[N], turn = 0;
set<pii> st;
bool cmp(int u, int v){
return mn[u] < mn[v];
}
bool pmc(int u, int v){
return ord[u] < ord[v];
}
void p_dfs(int v, int p = 0){
par[v][0] = p;
for(int i=1; i<LOG; i++)
par[v][i] = par[par[v][i - 1]][i - 1];
mn[v] = v;
for(auto u : adj[v]){
p_dfs(u, v);
mn[v] = min(mn[v], mn[u]);
}
sort(adj[v].begin(), adj[v].end(), cmp);
}
void dfs(int v){
for(auto u : adj[v])
dfs(u);
ord[v] = turn++;
}
int add(){
int v = (*st.begin()).S;
st.erase(st.begin());
full[v] = true;
return v;
}
int erase(int v){
int ans = 0;
for(int i=LOG-1; i>=0; i--){
if(full[par[v][i]]){
ans += (1 << i);
v = par[v][i];
}
}
full[v] = false;
st.insert({ord[v], v});
return ans;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int q; cin >> n >> q;
for(int i=1; i<=n; i++){
int p; cin >> p;
if(p == 0)root = i;
else adj[p].pb(i);
}
p_dfs(root);
dfs(root);
for(int i=0; i<n; i++)
g[i] = i + 1;
sort(g, g + n, pmc);
for(int i=1; i<=n; i++)
st.insert({ord[i], i});
while(q--){
int tp; cin >> tp;
if(tp == 1){
int k, pos = -1; cin >> k;
while(k--)
pos = add();
cout << pos << '\n';
}else{
int v; cin >> v;
cout << erase(v) << '\n';
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
12832 KB |
Output is correct |
2 |
Runtime error |
63 ms |
16924 KB |
Execution killed because of forbidden syscall writev (20) |
3 |
Runtime error |
69 ms |
16924 KB |
Execution killed because of forbidden syscall writev (20) |
4 |
Correct |
0 ms |
12832 KB |
Output is correct |
5 |
Correct |
0 ms |
12832 KB |
Output is correct |
6 |
Correct |
0 ms |
12832 KB |
Output is correct |
7 |
Correct |
0 ms |
12832 KB |
Output is correct |
8 |
Correct |
0 ms |
12832 KB |
Output is correct |
9 |
Runtime error |
3 ms |
13096 KB |
Execution killed because of forbidden syscall writev (20) |
10 |
Runtime error |
16 ms |
13888 KB |
Execution killed because of forbidden syscall writev (20) |
11 |
Runtime error |
79 ms |
16924 KB |
Execution killed because of forbidden syscall writev (20) |
12 |
Runtime error |
66 ms |
16924 KB |
Execution killed because of forbidden syscall writev (20) |
13 |
Runtime error |
86 ms |
16924 KB |
Execution killed because of forbidden syscall writev (20) |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
23 ms |
15580 KB |
Execution killed because of forbidden syscall writev (20) |
2 |
Runtime error |
116 ms |
23204 KB |
Execution killed because of forbidden syscall writev (20) |
3 |
Runtime error |
113 ms |
18900 KB |
Execution killed because of forbidden syscall writev (20) |
4 |
Runtime error |
26 ms |
15992 KB |
Execution killed because of forbidden syscall writev (20) |
5 |
Runtime error |
29 ms |
15856 KB |
Execution killed because of forbidden syscall writev (20) |
6 |
Runtime error |
23 ms |
15852 KB |
Execution killed because of forbidden syscall writev (20) |
7 |
Runtime error |
29 ms |
15096 KB |
Execution killed because of forbidden syscall writev (20) |
8 |
Runtime error |
13 ms |
15588 KB |
Execution killed because of forbidden syscall writev (20) |
9 |
Runtime error |
193 ms |
23608 KB |
Execution killed because of forbidden syscall writev (20) |
10 |
Runtime error |
183 ms |
23212 KB |
Execution killed because of forbidden syscall writev (20) |
11 |
Runtime error |
139 ms |
23212 KB |
Execution killed because of forbidden syscall writev (20) |
12 |
Runtime error |
203 ms |
21080 KB |
Execution killed because of forbidden syscall writev (20) |
13 |
Runtime error |
186 ms |
26464 KB |
Execution killed because of forbidden syscall writev (20) |
14 |
Runtime error |
133 ms |
18900 KB |
Execution killed because of forbidden syscall writev (20) |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
39 ms |
18092 KB |
Execution killed because of forbidden syscall writev (20) |
2 |
Runtime error |
189 ms |
21260 KB |
Execution killed because of forbidden syscall writev (20) |
3 |
Runtime error |
129 ms |
25160 KB |
Execution killed because of forbidden syscall writev (20) |
4 |
Runtime error |
129 ms |
21508 KB |
Execution killed because of forbidden syscall writev (20) |
5 |
Runtime error |
146 ms |
21112 KB |
Execution killed because of forbidden syscall writev (20) |
6 |
Runtime error |
86 ms |
21108 KB |
Execution killed because of forbidden syscall writev (20) |
7 |
Runtime error |
86 ms |
19548 KB |
Execution killed because of forbidden syscall writev (20) |
8 |
Runtime error |
76 ms |
25160 KB |
Execution killed because of forbidden syscall writev (20) |
9 |
Runtime error |
106 ms |
23612 KB |
Execution killed because of forbidden syscall writev (20) |
10 |
Runtime error |
116 ms |
23216 KB |
Execution killed because of forbidden syscall writev (20) |
11 |
Runtime error |
199 ms |
23212 KB |
Execution killed because of forbidden syscall writev (20) |
12 |
Runtime error |
183 ms |
21260 KB |
Execution killed because of forbidden syscall writev (20) |
13 |
Runtime error |
196 ms |
28304 KB |
Execution killed because of forbidden syscall writev (20) |
14 |
Runtime error |
103 ms |
18900 KB |
Execution killed because of forbidden syscall writev (20) |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
163 ms |
23612 KB |
Execution killed because of forbidden syscall writev (20) |
2 |
Runtime error |
176 ms |
21256 KB |
Execution killed because of forbidden syscall writev (20) |
3 |
Runtime error |
196 ms |
28304 KB |
Execution killed because of forbidden syscall writev (20) |
4 |
Runtime error |
159 ms |
23608 KB |
Execution killed because of forbidden syscall writev (20) |
5 |
Runtime error |
206 ms |
23208 KB |
Execution killed because of forbidden syscall writev (20) |
6 |
Runtime error |
206 ms |
23216 KB |
Execution killed because of forbidden syscall writev (20) |
7 |
Runtime error |
206 ms |
21264 KB |
Execution killed because of forbidden syscall writev (20) |
8 |
Runtime error |
169 ms |
28308 KB |
Execution killed because of forbidden syscall writev (20) |
9 |
Runtime error |
76 ms |
18900 KB |
Execution killed because of forbidden syscall writev (20) |