#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[200001][21];
int dp[200005][21];
bool id[200005];
int lvl[200005];
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 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 (k < (1 << i)) continue ;
k -= (1 << i);
a = dp[a][i];
}
return a;
}
bool check(int x, int y, int k, int a) {
if (dp[dq[x][0][0]][k] != a) return 0;
return 1;
}
void cut(int x) {
int y = dp[x][0];
for (int i = 0; i <= 20; i++) {
for (auto l: dq[y][i]) {
if (!check(l, y, i, x)) continue ;
for (int j = i; j <= 20; j++) {
dp[l][j] = 0;
}
}
}
}
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;
int in[100001];
for (int i = 1; i <= n; i++) {
cin >> dp[i][0];
in[dp[i][0]] = 1;
dq[dp[i][0]][0].pb(i);
}
for (int i = 1, m = n; i <= m; i++) if (!in[i]) {
dp[++n][0] = i;
dq[i][0].pb(n);
}
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 |
Runtime error |
15 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
