#include<stdio.h>
#include<vector>
#define M 100010
using namespace std;
vector<int>con[M];
int val,sw,m,pos[M],k,anc,s1,s2,lev[M],t=1,n,ch[M],a[M],root[M],w,s[M],e[M],cnt,d[21][M];
struct data{
int x,ch;
}tree[M*5];
void dfs(int x){
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){
s[x]=++cnt; lev[x]=h;
for(int 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=max(tree[k*2].ch,tree[k].ch);
tree[k*2+1].ch=max(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<=17;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 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");
}
}
int main(){
int i,j,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);
}
for(i=1;i<=17;i++){
for(j=1;j<=n;j++){
d[i][j]=d[i-1][d[i-1][j]];
}
}
scanf("%d",&m);
for(i=1;i<=m;i++){
scanf("%d",&x);
if(x==1){
scanf("%d",&y);
update(1,t,1,s[y],e[y],s[y]);
}
else{
scanf("%d %d",&y,&z);
pro2(y,z);
}
}
return 0;
}
Compilation message
specialg.cpp: In function 'void dfs2(int, int)':
specialg.cpp:19:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<con[x].size();i++) dfs2(con[x][i],h+1);
~^~~~~~~~~~~~~~
specialg.cpp: In function 'int main()':
specialg.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
specialg.cpp:70:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i]);
~~~~~^~~~~~~~~~~~
specialg.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&m);
~~~~~^~~~~~~~~
specialg.cpp:85:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
~~~~~^~~~~~~~~
specialg.cpp:87:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&y);
~~~~~^~~~~~~~~
specialg.cpp:91:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&y,&z);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
2940 KB |
Output is correct |
| 2 |
Correct |
8 ms |
3324 KB |
Output is correct |
| 3 |
Correct |
8 ms |
3324 KB |
Output is correct |
| 4 |
Correct |
15 ms |
3324 KB |
Output is correct |
| 5 |
Correct |
9 ms |
3376 KB |
Output is correct |
| 6 |
Correct |
25 ms |
3680 KB |
Output is correct |
| 7 |
Correct |
26 ms |
3884 KB |
Output is correct |
| 8 |
Correct |
27 ms |
4204 KB |
Output is correct |
| 9 |
Correct |
28 ms |
4380 KB |
Output is correct |
| 10 |
Correct |
25 ms |
4744 KB |
Output is correct |
| 11 |
Correct |
268 ms |
26736 KB |
Output is correct |
| 12 |
Correct |
180 ms |
26736 KB |
Output is correct |
| 13 |
Correct |
258 ms |
26736 KB |
Output is correct |
| 14 |
Correct |
148 ms |
26736 KB |
Output is correct |
| 15 |
Correct |
170 ms |
26736 KB |
Output is correct |
| 16 |
Correct |
170 ms |
26736 KB |
Output is correct |
| 17 |
Correct |
231 ms |
35884 KB |
Output is correct |
| 18 |
Correct |
222 ms |
37904 KB |
Output is correct |
| 19 |
Correct |
222 ms |
39908 KB |
Output is correct |
| 20 |
Correct |
272 ms |
43676 KB |
Output is correct |
