oj.uz

Submission #13143

# Submission time Handle Problem Language Result Execution time Memory
13143 2015-01-31T17:03:03 Z dohyun0324 Special graph (IZhO13_specialg) C++
100 / 100
 230 ms 26004 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18404 KB Output is correct
2 Correct 3 ms 18404 KB Output is correct
3 Correct 0 ms 18404 KB Output is correct
4 Correct 15 ms 18404 KB Output is correct
5 Correct 4 ms 18404 KB Output is correct
6 Correct 13 ms 18404 KB Output is correct
7 Correct 23 ms 18404 KB Output is correct
8 Correct 19 ms 18404 KB Output is correct
9 Correct 26 ms 18404 KB Output is correct
10 Correct 15 ms 18404 KB Output is correct
11 Correct 230 ms 26004 KB Output is correct
12 Correct 162 ms 21644 KB Output is correct
13 Correct 172 ms 22884 KB Output is correct
14 Correct 162 ms 21228 KB Output is correct
15 Correct 173 ms 21888 KB Output is correct
16 Correct 157 ms 21680 KB Output is correct
17 Correct 190 ms 24172 KB Output is correct
18 Correct 200 ms 24168 KB Output is correct
19 Correct 202 ms 24168 KB Output is correct
20 Correct 207 ms 26000 KB Output is correct