#include<stdio.h>
const int N_ = 100010;
const int T_ = 1<<17;
int st[N_], en[N_<<1], nxt[N_<<1];
inline void addE(int s,int e,int c){nxt[c]=st[s],st[s]=c,en[c]=e;}
int ind[N_], p[N_], er[N_];
int N, M;
int S[N_], D[N_], U[N_], dep[N_], ns = 1;
int Que[N_];
int cn[N_], us[N_], ue[N_], nc;
int qua[N_][3];
int ans[N_], len;
int T[1<<18];
struct UnF{
int p[N_], w[N_];
void init(){for(int i=1;i<=N;i++)p[i] = i, w[i] = 1;}
int Find(int x){
if(x == p[x])return x;
return p[x] = Find(p[x]);
}
void Union(int x,int y){
x = Find(x), y = Find(y);
if(x==y)return;
else if(w[x]<w[y])p[x] = y, w[y] += w[x];
else p[y] = x, w[x] += w[y];
}
}uf;
void update(int x)
{
x += T_;
while(x)T[x]++, x>>=1;
}
bool read(int a,int b)
{
a += T_, b += T_;
int cnt = 0, save = b-a+1;
while(a<=b){
if(a&1)cnt += T[a];
if(!(b&1))cnt += T[b];
a = (a+1)>>1;
b = (b-1)>>1;
}
return cnt == save;
}
void pushup()
{
int i;
int *fr = Que, *re = Que;
for(i=1;i<=N;i++)if(!ind[i])*fr++ = i;
while(fr!=re){
int t = *re++;
ind[p[t]]--;
if(!ind[p[t]])*fr++ = p[t];
}
}
inline bool c_ances(int x,int y){return S[x]<=D[y]&&D[y]<=D[x];}
void pushdown(int x,int f)
{
S[x] = ns;
U[x] = f;
for(int i=st[x];i;i=nxt[i])
if(!ind[en[i]] && !S[en[i]]){
dep[en[i]] = dep[x] + 1;
pushdown(en[i],f);
}
D[x] = ns++;
}
void cyc(int x,int s)
{
pushdown(x,x);
us[x] = s;
cn[x] = ++nc;
if(!cn[p[x]])cyc(p[x],s);
ue[x] = nc;
}
int solve(int a,int b)
{
if(uf.Find(a) != uf.Find(b))return -1;
if(c_ances(b,a))return dep[a] - dep[b];
if(!ind[b])return -1;
int ret = dep[a];
a = U[a];
if(!ind[a])return -1;
if(ue[a] < cn[b] || ue[b] < cn[a])return -1;
if(cn[a] < cn[b] && read(cn[a],cn[b]-1))return ret + cn[b] - cn[a];
if(cn[a] > cn[b] && read(cn[a],ue[a]) && read(us[a],cn[b]-1))return ret + 1 + ue[a] - us[a] - cn[a] + cn[b];
return -1;
}
int main()
{
scanf("%d",&N);
int i;
for(i=1;i<=N;i++){
scanf("%d",p+i);
if(p[i])addE(i,p[i],i<<1), addE(p[i],i,i<<1|1), ind[p[i]]++;
}
pushup();
for(i=1;i<=N;i++)if(ind[i] && !cn[i])cyc(i,nc+1);
for(i=1;i<=N;i++)if(!p[i])pushdown(i,i);
scanf("%d",&M);
for(i=1;i<=M;i++){
scanf("%d%d",qua[i],qua[i]+1);
if(qua[i][0] == 2)scanf("%d",qua[i]+2);
else er[qua[i][1]] = i;
}
uf.init();
for(i=1;i<=N;i++)if(p[i] && !er[i]){
if(ind[i])update(cn[i]);
uf.Union(i,p[i]);
}
for(i=M;i;i--){
if(qua[i][0] == 1){
uf.Union(qua[i][1],p[qua[i][1]]);
if(ind[qua[i][1]])update(cn[qua[i][1]]);
}
else ans[len++] = solve(qua[i][1],qua[i][2]);
}
for(i=len-1;i>=0;i--)printf("%d\n",ans[i]);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
10704 KB |
Output is correct |
| 2 |
Correct |
0 ms |
10704 KB |
Output is correct |
| 3 |
Correct |
0 ms |
10704 KB |
Output is correct |
| 4 |
Correct |
4 ms |
10704 KB |
Output is correct |
| 5 |
Correct |
0 ms |
10704 KB |
Output is correct |
| 6 |
Correct |
12 ms |
10704 KB |
Output is correct |
| 7 |
Correct |
12 ms |
10704 KB |
Output is correct |
| 8 |
Correct |
12 ms |
10704 KB |
Output is correct |
| 9 |
Correct |
12 ms |
10704 KB |
Output is correct |
| 10 |
Correct |
4 ms |
10704 KB |
Output is correct |
| 11 |
Correct |
80 ms |
13704 KB |
Output is correct |
| 12 |
Correct |
68 ms |
11488 KB |
Output is correct |
| 13 |
Correct |
80 ms |
11804 KB |
Output is correct |
| 14 |
Correct |
68 ms |
11364 KB |
Output is correct |
| 15 |
Correct |
68 ms |
11532 KB |
Output is correct |
| 16 |
Correct |
72 ms |
11508 KB |
Output is correct |
| 17 |
Correct |
92 ms |
12136 KB |
Output is correct |
| 18 |
Correct |
80 ms |
12144 KB |
Output is correct |
| 19 |
Correct |
80 ms |
12144 KB |
Output is correct |
| 20 |
Correct |
84 ms |
13704 KB |
Output is correct |
