oj.uz

답안 #13142

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13142 2015-01-31T16:57:56 Z dohyun0324 특수한 그래프 (IZhO13_specialg) C++
20 / 100
 231 ms 24048 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[250010];
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=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
20.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 16448 KB Output isn't correct
2 Incorrect 7 ms 16448 KB Output isn't correct
3 Incorrect 7 ms 16448 KB Output isn't correct
4 Incorrect 14 ms 16448 KB Output isn't correct
5 Incorrect 3 ms 16448 KB Output isn't correct
6 Incorrect 23 ms 16448 KB Output isn't correct
7 Incorrect 23 ms 16448 KB Output isn't correct
8 Incorrect 27 ms 16448 KB Output isn't correct
9 Incorrect 22 ms 16448 KB Output isn't correct
10 Incorrect 28 ms 16448 KB Output isn't correct
11 Incorrect 231 ms 24044 KB Output isn't correct
12 Correct 159 ms 19684 KB Output is correct
13 Incorrect 177 ms 20928 KB Output isn't correct
14 Correct 164 ms 19280 KB Output is correct
15 Correct 178 ms 19928 KB Output is correct
16 Correct 210 ms 19728 KB Output is correct
17 Incorrect 225 ms 22216 KB Output isn't correct
18 Incorrect 205 ms 22216 KB Output isn't correct
19 Incorrect 221 ms 22212 KB Output isn't correct
20 Incorrect 204 ms 24048 KB Output isn't correct