Cod sursa(job #66232)

Utilizator sealTudose Vlad seal Data 16 iunie 2007 19:04:12
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 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;
}