oj.uz

답안 #13132

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13132 2015-01-31T16:08:08 Z dohyun0324 특수한 그래프 (IZhO13_specialg) C++
0 / 100
 229 ms 23656 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,tree[k].ch);
        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 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],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 3 ms 16060 KB Output isn't correct
2 Incorrect 2 ms 16060 KB Output isn't correct
3 Incorrect 0 ms 16060 KB Output isn't correct
4 Incorrect 9 ms 16060 KB Output isn't correct
5 Incorrect 5 ms 16060 KB Output isn't correct
6 Incorrect 27 ms 16060 KB Output isn't correct
7 Incorrect 23 ms 16060 KB Output isn't correct
8 Incorrect 26 ms 16060 KB Output isn't correct
9 Incorrect 23 ms 16060 KB Output isn't correct
10 Incorrect 24 ms 16060 KB Output isn't correct
11 Incorrect 197 ms 23656 KB Output isn't correct
12 Incorrect 179 ms 19292 KB Output isn't correct
13 Incorrect 187 ms 20544 KB Output isn't correct
14 Incorrect 153 ms 18888 KB Output isn't correct
15 Incorrect 168 ms 19540 KB Output isn't correct
16 Incorrect 178 ms 19340 KB Output isn't correct
17 Incorrect 196 ms 21824 KB Output isn't correct
18 Incorrect 192 ms 21828 KB Output isn't correct
19 Incorrect 198 ms 21828 KB Output isn't correct
20 Incorrect 229 ms 23656 KB Output isn't correct