Cod sursa(job #1644041)

Utilizator alexpascadiAlexandru Pascadi alexpascadi Data 9 martie 2016 21:20:23
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.57 kb
#include <stdio.h>

using namespace std;

const int N = 32002;
const int LOG = 16;

int val[2*N],urm[2*N],cost[2*N],lst[N],nr=1;
int nod[N][LOG],v[N][LOG];
int uc[N],niv[N];

void adauga(int x, int y, int c)
{
    cost[nr]=c;
    val[nr]=y;
    urm[nr]=lst[x];
    lst[x]=nr;
    nr++;
}

int minim(int x, int y)
{
    if(x<y) return x;
    return y;
}

void init(int t, int x)
{
    int p=lst[x],y;
    while(p!=0)
    {
        y=val[p];
        if(y!=t)
        {
            uc[y]=cost[p];
            init(x,y);
        }
        p=urm[p];
    }
}

void dfs(int t, int x, int nivel)
{
    niv[x]=nivel;
    int k,p=lst[x],y;

    nod[x][0]=t; v[x][0]=uc[x];
    for(k=1;(1<<k)<=nivel;k++)
    {
        nod[x][k]=nod[nod[x][k-1]][k-1];
        v[x][k]=minim(v[x][k-1],v[nod[x][k-1]][k-1]);
    }

    while(p!=0)
    {
        y=val[p];
        if(y!=t)
            dfs(x,y,nivel+1);
        p=urm[p];
    }
}

int main()
{
    FILE *in=fopen("atac.in","r");
    FILE *out=fopen("atac.out","w");

    int n,m,p,i,j,x,y,z,aux,co,a,b,c,d,dist;
    fscanf(in,"%d%d%d",&n,&m,&p);

    for(i=2;i<=n;i++)
    {
        fscanf(in,"%d%d",&y,&co);
        adauga(i,y,co);
        adauga(y,i,co);
    }

    init(0,1);
    dfs(0,1,0);

    fscanf(in,"%d%d%d%d%d%d",&x,&y,&a,&b,&c,&d);
    for(i=m;i>=1;i--)
    {
        //calc z
        //printf("x=%d, y=%d\n",x,y);
        if(x==y) z=0;
        else
        {
            if(niv[x]>niv[y]) {aux=x; x=y; y=aux;}
            z=uc[y];
            //adu y la nivelul lui x
            dist=niv[y]-niv[x];
            for(j=0;(1<<j)<=dist;j++)
            {
                if((1<<j)&dist)
                {
                    z=minim(z,v[y][j]);
                    y=nod[y][j];
                }
            }
            //printf("x=%d, y=%d, z=%d\n",x,y,z);
            //ridica si x si y
            for(j=16;j>=0;j--)
            {
                if((1<<j)<=niv[x] && nod[x][j]!=nod[y][j])
                {
                    z=minim(z,v[x][j]);
                    z=minim(z,v[y][j]);
                    x=nod[x][j];
                    y=nod[y][j];
                }
            }
            //printf("x=%d, y=%d, z=%d\n",x,y,z);
            if(x!=1 && x!=y)
            {
                z=minim(z,uc[x]); //printf("x=%d, uc[x]=%d\n",x,uc[x]);
                z=minim(z,uc[y]); //printf("y=%d, uc[y]=%d\n",y,uc[y]);
            }
        }
        //printf("final: z=%d\n",z);
        if(i<=p) fprintf(out,"%d\n",z);
        //calc noile x si y
        x=(x*a + y*b)%n + 1;
        y=(y*c + z*d)%n + 1;
    }

    return 0;
}