Submission #13143

#	Time	Username	Problem	Language	Result	Execution time	Memory
13143		dohyun0324	Special graph (IZhO13_specialg)	C++98	100 / 100	230 ms	26004 KiB

specialg

#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[500010];
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<=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;
}

• Subtask 1: 100 / 100