Cod sursa(job #931169)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 28 martie 2013 00:57:07
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb

#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream in ("atac.in");
ofstream out ("atac.out");

const int N = 32001;

int n,m,p,X,Y,A,B,C,D,T[16][N],COST[16][N],lvl[N],log[N];
vector<pair<int,int> > G[N];

void READ ()
{

    in>>n>>m>>p;

    for( int x,c,i=2 ; i <= n ; ++i )
    {

        in>>x>>c;

        G[i].push_back(make_pair(x,c));
        G[x].push_back(make_pair(i,c));

    }

    in>>X>>Y>>A>>B>>C>>D;

}

void DFS (int nod)
{

    for( vector<pair<int,int> >::iterator it=G[nod].begin() ; it < G[nod].end() ; ++it )
        if( T[0][nod] != it->first )
        {

            T[0][it->first]=nod;
            COST[0][it->first]=it->second;
            lvl[it->first]=lvl[nod]+1;
            DFS (it->first);

        }

}

int LCA ( int nod1 , int nod2 )
{

    for( ; lvl[nod1] < lvl[nod2] ; nod2=T[log[lvl[nod2]-lvl[nod1]]][nod2] );
    for( ; lvl[nod2] < lvl[nod1] ; nod1=T[log[lvl[nod1]-lvl[nod2]]][nod1] );

    if( nod1 == nod2)
        return nod1;

    for( int i=log[lvl[nod1]] ; i>=0 ; --i )
        if( T[i][nod1] != T[i][nod2] )
        {
            nod1=T[i][nod1];
            nod2=T[i][nod2];
        }

    return T[0][nod1];

}

int GET ( int nod , int Ds )
{

    int mn=1<<30;

    for( ; Ds ; Ds-=(1<<log[Ds]) )
    {

        mn=min(mn,COST[log[Ds]][nod]);
        nod=T[log[Ds]][nod];

    }

    return mn;

}

int QUERY ( int nod1 , int nod2 )
{

    if( nod1 == nod2 )
        return 0;

    int F=LCA(nod1,nod2);

    int mnd1=GET( nod1 , lvl[nod1]-lvl[F] );
    int mnd2=GET( nod2 , lvl[nod2]-lvl[F] );

    return min(mnd1,mnd2);

}

void SOLVE ()
{

    for( int i=2 ; i <= n ; ++i )
        log[i]=log[i>>1]+1;

    for( int i=1 ; i <= log[n] ; ++i )
        for( int j=1 ; j <= n ; ++j )
        {

            T[i][j]=T[i-1][T[i-1][j]];
            COST[i][j]=min(COST[i-1][j],COST[i-1][T[i-1][j]]);

        }

    for( ; m > p ; --m )
    {

        int Z=QUERY(X,Y);
        X=(A*X+Y*B)%n+1;
        Y=(Y*C+Z*D)%n+1;

    }

}

void PRINT ()
{

     for( ; m ; --m )
    {

        int SOL=QUERY(X,Y);
        X=(A*X+B*Y)%n+1;
        Y=(C*Y+D*SOL)%n+1;

        out<<SOL<<'\n';

    }

}

int main ()
{

    READ ();
    DFS (1);
    SOLVE ();
    PRINT ();

    return 0;

}