oj.uz

Submission #13144

# Submission time Handle Problem Language Result Execution time Memory
13144 2015-01-31T17:09:03 Z dohyun0324 Special graph (IZhO13_specialg) C++
100 / 100
 224 ms 26004 KB 
#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){
    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=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;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 18404 KB Output is correct
2 Correct 3 ms 18404 KB Output is correct
3 Correct 7 ms 18404 KB Output is correct
4 Correct 10 ms 18404 KB Output is correct
5 Correct 3 ms 18404 KB Output is correct
6 Correct 23 ms 18404 KB Output is correct
7 Correct 13 ms 18404 KB Output is correct
8 Correct 26 ms 18404 KB Output is correct
9 Correct 24 ms 18404 KB Output is correct
10 Correct 20 ms 18404 KB Output is correct
11 Correct 214 ms 26004 KB Output is correct
12 Correct 170 ms 21644 KB Output is correct
13 Correct 188 ms 22888 KB Output is correct
14 Correct 158 ms 21232 KB Output is correct
15 Correct 168 ms 21888 KB Output is correct
16 Correct 155 ms 21684 KB Output is correct
17 Correct 199 ms 24168 KB Output is correct
18 Correct 190 ms 24168 KB Output is correct
19 Correct 185 ms 24168 KB Output is correct
20 Correct 224 ms 26000 KB Output is correct