이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e5+5;
const int INV = -1;
int N, Q;
vector<int> adj[maxn];
int minsub[maxn];
int ord[maxn], inv[maxn]; //node to seg, seg to node
int pt = 1;
int seg[maxn];
void prep(int i) {
minsub[i] = i;
for (int j: adj[i]) {
minsub[i] = min(minsub[i],minsub[j]);
}
sort(adj[i].begin(),adj[i].end(),[](int a, int b) {
return minsub[a] < minsub[b];
});
}
void dfs(int i) {
for (int j: adj[i]) {
dfs(j);
}
ord[i] = pt;
inv[pt] = i;
pt++;
//cout << i << ' ';
}
const int maxk = 18;
int par[maxk][maxn];
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> N >> Q;
int rt = -1;
for (int i = 1; i <= N; i++) {
int pi; cin >> pi;
if (pi == 0) rt = i;
else adj[pi].push_back(i);
par[0][i] = pi;
}
for (int k = 1; k < maxk; k++) {
for (int i = 1; i <= N; i++) {
par[k][i] = par[k-1][par[k-1][i]];
}
}
prep(rt);
dfs(rt);
for (int i = 1; i <= N; i++) {
seg[i] = 1;
}
while (Q--) {
int t; cin >> t;
if (t == 1) {
int k; cin >> k;
int sum = 0;
for (int i = 1; i <= N; i++) {
sum += seg[i];
if (sum == k) {
for (int j = 1; j <= i; j++) {
seg[j] = 0;
}
cout << inv[i] << '\n';
break;
}
}
}
else {
int v; cin >> v;
int res = 0;
for (int k = maxk - 1; k >= 0; k--) {
if (par[k][v] == 0) continue;
int nxt = par[k][v];
if (seg[ord[nxt]] == 0) {
res += (1<<k);
v = nxt;
}
}
seg[ord[v]] = 1;
cout << res << '\n';
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |