#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second
#define sp << ' ' <<
#define nl << '\n'
using namespace std;
vector<int> dq[100001][21];
int dp[100005][21];
bool id[100005];
int lvl[100005];
int n, q;
void dfs(int s) {
if (id[s]) return;
id[s] = 1;
dfs(dp[s][0]);
lvl[s] = lvl[dp[s][0]] + 1;
}
void prep() {
for (int i = 0; i <= 20; i++) dp[0][i] = -1;
for (int j = 1; j <= 20; j++)
for (int i = 1; i <= n; i++) {
dp[i][j] = dp[dp[i][j-1]][j-1];
dq[dp[dp[i][j-1]][j-1]][j].pb(i);
}
for (int i = 1; i <= n; i++) if (!id[i]) dfs(i);
}
int jump(int a, int k) {
if (k <= 0) return a;
for (int i = 20; i >= 0; i--) {
if ((1 << i) > k) continue ;
k -= (1 << i);
a = dp[a][i];
}
return a;
}
void cut(int x) {
for (int i = 0; i <= 20; i++) {
for (auto l: dq[x][i]) {
for (int j = i; j <= 20; j++) {
dp[l][j] = -1;
}
}
dp[x][i] = -1;
}
}
int find(int x, int y) {
int a = jump(x, lvl[x]);
if (jump(x, lvl[x] - lvl[y]) == y) return lvl[x] - lvl[y];
if (jump(a, lvl[a] - lvl[y]) == y) return lvl[x] + lvl[a] - lvl[y];
return -1;
}
void solve(){
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> dp[i][0];
if (!dp[i][0]) dp[i][0] = -1;
dq[dp[i][0]][0].pb(i);
}
prep();
cin >> q;
while (q--) {
int t; cin >> t;
if (t == 1) {
int x; cin >> x;
cut(x);
}
else {
int x, y; cin >> x >> y;
cout << find(x, y) nl;
}
}
}
signed main() {IOS solve(); return 0;}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
41 ms |
50248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
