Cod sursa(job #886846)

Utilizator stoicatheoFlirk Navok stoicatheo Data 23 februarie 2013 12:45:34
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include<stdio.h>
#include<stdlib.h>
#define Nm 32001
#define LognM 15
#define Mm 500000
#define Inf 100001
#define min(a,b) ((a)<(b)?(a):(b))
int *G[Nm],*C[Nm],D[Nm],n;
int An[LognM][Nm],Cm[LognM][Nm],Lv[Nm];
int A[Mm],m,p,x,y,a,b,c,d,logn;

void read()
{
    int i,j,cost;

    freopen("atac.in","r",stdin);
    scanf("%d%d%d",&n,&m,&p);
    for(i=2;i<=n;++i)
    {
    scanf("%d%d",&j,&cost);
    G[i]=(int*)realloc(G[i],(D[i]+1)*sizeof(int));
    C[i]=(int*)realloc(C[i],(D[i]+1)*sizeof(int));
    G[i][D[i]]=j;
    C[i][D[i]++]=cost;
    G[j]=(int*)realloc(G[j],(D[j]+1)*sizeof(int));
    C[j]=(int*)realloc(C[j],(D[j]+1)*sizeof(int));
    G[j][D[j]]=i;
    C[j][D[j]++]=cost;
    }
    scanf("%d%d%d%d%d%d",&x,&y,&a,&b,&c,&d);
}

void DFS(int x, int fx, int c)
{
    int i;

    Lv[x]=Lv[fx]+1;
    An[0][x]=fx;
    Cm[0][x]=c;
    for(i=1;An[i-1][An[i-1][x]];++i)
    {
    An[i][x]=An[i-1][An[i-1][x]];
    Cm[i][x]=min(Cm[i-1][x],Cm[i-1][An[i-1][x]]);
    }

    for(i=0;i<D[x];++i)
    if(!Lv[G[x][i]])
        DFS(G[x][i],x,C[x][i]);
}

int minedge(int x, int y)
{
    int i,j,m=Inf;

    if(x==y)
    return 0;

    if(Lv[x]>Lv[y])
    {
    x=x^y;
    y=x^y;
    x=x^y;
    }

    j=Lv[y]-Lv[x];
    for(i=0;1<<i<=j;++i)
    if(1<<i&j)
    {
        m=min(m,Cm[i][y]);
        y=An[i][y];
    }

    if(x==y)
    return m;

    for(i=logn;i>=0;--i)
    if(An[i][x]!=An[i][y])
    {
        m=min(m,Cm[i][x]);
        m=min(m,Cm[i][y]);
        x=An[i][x];
        y=An[i][y];
    }
    m=min(m,Cm[0][x]);
    m=min(m,Cm[0][y]);
    return m;
}

void solve()
{
    int i;

    DFS(1,0,0);

    while(1<<logn+1<=n)
    ++logn;

    for(i=0;i<m;++i)
    {
    A[i]=minedge(x,y);
    x=(x*a+y*b)%n+1;
    y=(y*c+A[i]*d)%n+1;
    }
}

void write()
{
    int i;

    freopen("atac.out","w",stdout);
    for(i=m-p;i<m;++i)
    printf("%d\n",A[i]);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}