oj.uz

답안 #13134

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13134 2015-01-31T16:18:10 Z dohyun0324 특수한 그래프 (IZhO13_specialg) C++
0 / 100
 221 ms 23660 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[20][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){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"); return;}
    }
}
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
0.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 16060 KB Output isn't correct
2 Incorrect 6 ms 16060 KB Output isn't correct
3 Incorrect 8 ms 16060 KB Output isn't correct
4 Incorrect 10 ms 16060 KB Output isn't correct
5 Incorrect 8 ms 16060 KB Output isn't correct
6 Incorrect 21 ms 16060 KB Output isn't correct
7 Incorrect 25 ms 16060 KB Output isn't correct
8 Incorrect 22 ms 16060 KB Output isn't correct
9 Incorrect 21 ms 16060 KB Output isn't correct
10 Incorrect 22 ms 16060 KB Output isn't correct
11 Incorrect 219 ms 23660 KB Output isn't correct
12 Incorrect 172 ms 19292 KB Output isn't correct
13 Incorrect 176 ms 20540 KB Output isn't correct
14 Incorrect 175 ms 18884 KB Output isn't correct
15 Incorrect 174 ms 19540 KB Output isn't correct
16 Incorrect 218 ms 19340 KB Output isn't correct
17 Incorrect 215 ms 21824 KB Output isn't correct
18 Incorrect 221 ms 21828 KB Output isn't correct
19 Incorrect 216 ms 21828 KB Output isn't correct
20 Incorrect 219 ms 23660 KB Output isn't correct