Cod sursa(job #425052)

Utilizator MarkerOnicas Mircea Marker Data 25 martie 2010 14:21:22
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
#include <stdio.h>
#include <vector>
#define IN "atac.in"
#define OUT "atac.out"
#define Lg 32010
#define L 20
#define INF 0x3f3f3f3f

using namespace std;

struct lol
{
    int Dir,B;
}l;
int rmq[L][Lg*4];
int X,Y,A,B,C,D,Z,m,p,n;
vector <lol> V[Lg];
int Grad[Lg*4];
int Niv[Lg*4];
int Euler[Lg*4],nr;
int ap[Lg*4];
int viz[Lg];
int Bombe[Lg*4];
int put[Lg*4];
int T[Lg];
int Co[Lg];

void citire()
{
    scanf ("%d %d %d",&n,&m,&p);
    for (int i=2;i<=n;i++)
    {
        scanf ("%d %d",&l.Dir, &l.B);
        Grad[i]++;
        Grad[l.Dir]++;
        V[i].push_back(l);
        X=l.Dir;
        l.Dir=i;
        V[X].push_back(l);
    }
    scanf ("%d %d %d %d %d %d",&X,&Y,&A,&B,&C,&D);
}

void df(int nod)
{
    viz[nod]=1;
    for (int i=0;i<Grad[nod];i++)
        if (!viz[V[nod][i].Dir])
        {
            Euler[nr++]=V[nod][i].Dir;
            T[V[nod][i].Dir]=nod;
            Co[V[nod][i].Dir]=V[nod][i].B;
            if (ap[V[nod][i].Dir]==0)
                ap[V[nod][i].Dir]=nr-1;
            Niv[V[nod][i].Dir]=Niv[nod]+1;
            df(V[nod][i].Dir);
            Euler[nr++]=nod;
        }
}
int  mi(int a,int  b)
{
    return Niv[a]<Niv[b]?a:b;
}

void RMQ()
{
    int  n=nr;
    for (int i=2;i<=n;i++)
    {
        put[i]=put[i>>1]+1;
        rmq[0][i]=Euler[i];
    }
    rmq[0][1]=Euler[1];
    for (int i=1; i<=put[n];i++)
        for (int j=1;j<=n-(1<<(i))+1;j++)
            rmq[i][j]=mi(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
}

int mini(int a,int b)
{
    return a<b?a:b;
}

void solve()
{
    int X1,Y1,P,Nod;
    Euler[1]=1;
    ap[1]=1;
    Niv[1]=1;
    nr=2;
    df(1);
    RMQ();
    for (int i=1;i<=m;i++)
    {
        X1=X;
        Y1=Y;
        if (ap[X1]>ap[Y1])
        {
            int aux=X1;
            X1=Y1;
            Y1=aux;
        }
        P=put[ap[Y1]-ap[X1]+1];
        Nod=mi(rmq[P][ap[X1]], rmq[P][ap[Y1]-(1<<P)+1]);
        Z=0x3f3f3f3f;
        while (X1!=Nod)
        {
            Z=mini(Z,Co[X1]);
            X1=T[X1];
        }
        while (Y1!=Nod)
        {
            Z=mini(Z,Co[Y1]);
            Y1=T[Y1];
        }
        if (i+P>=m)
            printf("%d\n",Z);
        X=(X*A+Y*B)%n+1;
        Y=(Y*C+Z*D)%n+1;
    }
}

int main ()
{
    freopen (IN ,"r", stdin);
    freopen (OUT ,"w", stdout);
    citire();
    solve();
    return 0;
}