#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
#define N_ 100100
vector<int>E[N_];
int n, Q, w[N_], renum[N_], Cyc[N_][2], C, SZ[N_], v[N_], ed[N_], cnt, par[N_], Dep[N_], pp[N_], RR[N_];
bool Iscyc[N_];
struct Query{
int a, b, c;
}q[N_];
void DFS(int a, int P){
int i;
pp[a] = P;
renum[a] = ++cnt;
for (i = 0; i < E[a].size(); i++){
Dep[E[a][i]] = Dep[a] + 1;
DFS(E[a][i], P);
}
ed[renum[a]] = cnt;
}
int find(int a){
if (a == par[a])return a;
return par[a] = find(par[a]);
}
void Link(int a, int b){
int x = find(a), y = find(b);
if (x == y){
Iscyc[Cyc[x][0]] = true;
return;
}
par[x] = y;
find(a);
}
int dis(int x, int y){
int P = find(x), cc, dx, dy;
if (P != find(y))return -1;
if (renum[y] < renum[x] && ed[renum[y]] >= renum[x])return Dep[x] - Dep[y];
cc = Cyc[y][0];
if (!cc)return -1;
if (Iscyc[cc])return (Cyc[y][1] - Cyc[pp[x]][1] + SZ[cc]) % SZ[cc] + Dep[x];
dx = (Cyc[P][1] - Cyc[pp[x]][1] + SZ[cc]) % SZ[cc];
dy = (Cyc[P][1] - Cyc[y][1] + SZ[cc]) % SZ[cc];
if (dy > dx)return -1;
else return dx - dy + Dep[x];
}
int main()
{
int x, t, c, i, y;
scanf("%d", &n);
for (i = 1; i <= n; i++){
scanf("%d", &w[i]);
}
for (i = 1; i <= n; i++){
x = i;
t = cnt;
while (x && !v[x]){
v[x] = ++cnt;
x = w[x];
}
if (x && v[x]>t){
c = 0;
t = x;
Cyc[x][0] = ++C, Cyc[x][1] = c++;
while (w[x] != t){
x = w[x];
Cyc[x][0] = C, Cyc[x][1] = c++;
}
SZ[C] = c;
}
}
for (i = 1; i <= n; i++){
if (!Cyc[i][0]){
if(w[i])E[w[i]].push_back(i);
}
v[i] = 0;
}
cnt = 0;
for (i = 1; i <= n; i++){
if (Cyc[i][0] || !w[i])DFS(i, i);
par[i] = i;
}
scanf("%d", &Q);
for (i = 0; i < Q; i++){
scanf("%d%d", &q[i].a, &q[i].b);
if (q[i].a == 2)scanf("%d", &q[i].c);
else v[q[i].b] = 1;
}
for (i = 1; i <= n; i++){
if(!v[i] && w[i]) Link(i, w[i]);
}
cnt = 0;
for (i = Q - 1; i >= 0; i--){
if (q[i].a == 1){
Link(q[i].b, w[q[i].b]);
continue;
}
x = q[i].b, y = q[i].c;
RR[cnt++] = dis(x, y);
}
for (i = cnt - 1; i >= 0; i--)printf("%d\n", RR[i]);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
9128 KB |
Output is correct |
2 |
Correct |
0 ms |
9128 KB |
Output is correct |
3 |
Correct |
0 ms |
9128 KB |
Output is correct |
4 |
Correct |
4 ms |
9128 KB |
Output is correct |
5 |
Correct |
0 ms |
9128 KB |
Output is correct |
6 |
Correct |
8 ms |
9128 KB |
Output is correct |
7 |
Correct |
12 ms |
9128 KB |
Output is correct |
8 |
Correct |
8 ms |
9128 KB |
Output is correct |
9 |
Correct |
8 ms |
9128 KB |
Output is correct |
10 |
Correct |
12 ms |
9128 KB |
Output is correct |
11 |
Correct |
64 ms |
9148 KB |
Output is correct |
12 |
Correct |
68 ms |
10344 KB |
Output is correct |
13 |
Correct |
76 ms |
10848 KB |
Output is correct |
14 |
Correct |
68 ms |
10120 KB |
Output is correct |
15 |
Correct |
64 ms |
10384 KB |
Output is correct |
16 |
Correct |
68 ms |
10356 KB |
Output is correct |
17 |
Correct |
80 ms |
11360 KB |
Output is correct |
18 |
Correct |
64 ms |
11360 KB |
Output is correct |
19 |
Correct |
76 ms |
11360 KB |
Output is correct |
20 |
Correct |
64 ms |
9128 KB |
Output is correct |