oj.uz

답안 #13141

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13141 2015-01-31T16:42:13 Z dohyun0324 특수한 그래프 (IZhO13_specialg) C++
0 / 100
 245 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 || 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"); 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 3 ms 16060 KB Output isn't correct
3 Incorrect 0 ms 16060 KB Output isn't correct
4 Incorrect 14 ms 16060 KB Output isn't correct
5 Incorrect 3 ms 16060 KB Output isn't correct
6 Incorrect 22 ms 16060 KB Output isn't correct
7 Incorrect 23 ms 16060 KB Output isn't correct
8 Incorrect 15 ms 16060 KB Output isn't correct
9 Incorrect 20 ms 16060 KB Output isn't correct
10 Incorrect 24 ms 16060 KB Output isn't correct
11 Incorrect 230 ms 23660 KB Output isn't correct
12 Incorrect 179 ms 19292 KB Output isn't correct
13 Incorrect 170 ms 20540 KB Output isn't correct
14 Incorrect 162 ms 18892 KB Output isn't correct
15 Incorrect 173 ms 19548 KB Output isn't correct
16 Incorrect 165 ms 19344 KB Output isn't correct
17 Incorrect 198 ms 21824 KB Output isn't correct
18 Incorrect 215 ms 21828 KB Output isn't correct
19 Incorrect 202 ms 21824 KB Output isn't correct
20 Incorrect 245 ms 23656 KB Output isn't correct