#include<stdio.h>
#include<vector>
using namespace std;
vector<int>con[100010];
int val,sw,m,pos[100010],k,anc,s1,s2,lev[100010],t=1,n,ch[100010],a[100010],root[100010],w,s[100010],e[100010],cnt,d[21][100010];
struct data{
int x,ch;
}tree[250010];
void dfs(int x)
{
int i;
if(ch[x]) return;
ch[x]=k;
if(ch[a[x]]==k || a[x]==0){root[++w]=x; return;}
con[a[x]].push_back(x);
dfs(a[x]);
}
void dfs2(int x,int h)
{
int i;
s[x]=++cnt; lev[x]=h;
for(i=0;i<con[x].size();i++) dfs2(con[x][i],h+1);
e[x]=cnt;
}
int update(int x,int y,int k,int s,int e,int p)
{
if(tree[k].ch){
tree[k].x=max(tree[k].x,tree[k].ch);
tree[k*2].ch=tree[k*2+1].ch=tree[k].ch;
tree[k].ch=0;
}
if(s<=x && y<=e){
tree[k].x=max(tree[k].x,p);
tree[k*2].ch=max(tree[k*2].ch,p);
tree[k*2+1].ch=max(tree[k*2+1].ch,p);
return tree[k].x;
}
if(s>y || e<x) return 0;
return tree[k].x=max(update(x,(x+y)/2,k*2,s,e,p),update((x+y)/2+1,y,k*2+1,s,e,p));
}
int LCA(int x,int c)
{
int i;
for(i=0;i<=20;i++){
if((1<<i)&c) x=d[i][x];
}
return x;
}
void check(int x,int y)
{
int p;
p=LCA(x,lev[x]-lev[y]);
if(p!=y) return;
s1=update(1,t,1,s[x],s[x],0);
s2=update(1,t,1,s[y],s[y],0);
if(s1==s2){printf("%d\n",lev[x]-lev[y]+val); sw=1;}
}
void pro1(int x)
{
update(1,t,1,s[x],e[x],s[x]);
}
void pro2(int x,int y)
{
sw=0;
if(lev[x]>=lev[y]){val=0; check(x,y);}
if(sw==0)
{
s1=update(1,t,1,s[x],s[x],0); val=lev[x];
anc=LCA(x,lev[x]-1);
if(s1==0) x=a[anc];
if(lev[x]<lev[y]){printf("-1\n"); return;}
check(x,y);
if(sw==0) printf("-1\n");
}
}
void DP()
{
int i,j;
for(i=1;i<=20;i++){
for(j=1;j<=n;j++){
d[i][j]=d[i-1][d[i-1][j]];
}
}
}
int main()
{
int i,x,y,z;
scanf("%d",&n);
for(;;){if(t>=n) break; t*=2;}
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
d[0][i]=a[i];
}
for(i=1;i<=n;i++){k++; dfs(i);}
for(i=1;i<=w;i++){
d[0][root[i]]=0;
dfs2(root[i],1);
}
DP();
scanf("%d",&m);
for(i=1;i<=m;i++){
scanf("%d",&x);
if(x==1){
scanf("%d",&y);
pro1(y);
}
else{
scanf("%d %d",&y,&z);
pro2(y,z);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
16448 KB |
Output isn't correct |
| 2 |
Incorrect |
7 ms |
16448 KB |
Output isn't correct |
| 3 |
Incorrect |
7 ms |
16448 KB |
Output isn't correct |
| 4 |
Incorrect |
14 ms |
16448 KB |
Output isn't correct |
| 5 |
Incorrect |
3 ms |
16448 KB |
Output isn't correct |
| 6 |
Incorrect |
23 ms |
16448 KB |
Output isn't correct |
| 7 |
Incorrect |
23 ms |
16448 KB |
Output isn't correct |
| 8 |
Incorrect |
27 ms |
16448 KB |
Output isn't correct |
| 9 |
Incorrect |
22 ms |
16448 KB |
Output isn't correct |
| 10 |
Incorrect |
28 ms |
16448 KB |
Output isn't correct |
| 11 |
Incorrect |
231 ms |
24044 KB |
Output isn't correct |
| 12 |
Correct |
159 ms |
19684 KB |
Output is correct |
| 13 |
Incorrect |
177 ms |
20928 KB |
Output isn't correct |
| 14 |
Correct |
164 ms |
19280 KB |
Output is correct |
| 15 |
Correct |
178 ms |
19928 KB |
Output is correct |
| 16 |
Correct |
210 ms |
19728 KB |
Output is correct |
| 17 |
Incorrect |
225 ms |
22216 KB |
Output isn't correct |
| 18 |
Incorrect |
205 ms |
22216 KB |
Output isn't correct |
| 19 |
Incorrect |
221 ms |
22212 KB |
Output isn't correct |
| 20 |
Incorrect |
204 ms |
24048 KB |
Output isn't correct |
