Cod sursa(job #1033382)

Utilizator superman_01Avramescu Cristian superman_01 Data 16 noiembrie 2013 20:26:34
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>

#define MAX_SIZE 32005
#define INF 0x3f3f3f3f

using namespace std;

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

typedef vector < pair < int ,  int > > ::iterator IT ;
vector < pair < int ,  int > > G[MAX_SIZE];
int N , M , P, Level[MAX_SIZE];
int X , Y , A , B , C , D ;
bool used[MAX_SIZE];
int F[20][MAX_SIZE], RMQ[20][MAX_SIZE] , Log[MAX_SIZE];


void DepthFirstSearch ( int node )
{
	used[node] = true;
   for ( IT it = G[node].begin() ; it != G[node].end() ; ++it )
   {
	   if ( !used[ it->first]  )
	   {
		   F[0][it->first] = node ;
		   RMQ[0][it->first] = it->second ;
		   Level[it->first] = Level[node] + 1 ;
		   DepthFirstSearch ( it->first );
	   }
   }
}

int LCA ( int X , int Y )
{
	for ( ; Level[X] < Level[Y] ; Y = F[Log[Level[Y] - Level[X]]][Y]);
	for ( ; Level[Y] < Level[X] ; X = F[Log[Level[X] - Level[Y]]][X]);
	if ( X == Y ) return X;
	int i , j ;
	for ( i = Log[Level[X]] ; i >= 0 ; --i )
	{
		if ( F[i][X] != F[i][Y] )
		{
			X = F[i][X] ;
			Y = F[i][Y] ;
		}
	}
	return F[0][X];
}
int FindSol ( int X , int NrLevels )
{
	int Sol = INF;
	while ( NrLevels > 0 )
	{
		Sol = min ( Sol , RMQ[Log[NrLevels]][X]);
		X = F[Log[NrLevels]][X];
		NrLevels -= ( 1 << Log[NrLevels] );
	}
	return Sol;
}
int Query ( int X , int Y )
{
	if ( X == Y ) return 0;
	int Node = LCA ( X , Y );
	int Sol;
	Sol = min ( FindSol( X , Level[X] - Level[Node]) , FindSol ( Y , Level[Y] - Level[Node]) );
	return Sol ;
}
void BuildRMQ ( void )
{
	int i , j , k ;
	for ( i = 1 ; i <= Log[N] ; ++i )
	{
		for ( j = 1 ; j <= N ; ++j )
		{
			F[i][j] = F[i-1][F[i-1][j]];
			RMQ[i][j] = min ( RMQ[i-1][j] , RMQ[i-1][F[i-1][j]] ) ;
		}
	}
	
}
int main ( void )
{
	int i , j , x , cost;
	in >> N >> M >> P ;
	for ( i = 2 ; i <= N ; ++i )
	{
		in >> x >> cost;
		G[i].push_back ( make_pair ( x , cost ) );
		G[x].push_back ( make_pair ( i , cost ) ); 
	}
	in >> X >> Y >> A >> B >> C >> D;
	for ( i = 2 ; i <= N ; ++i )
		Log[i] = Log[i/2] + 1 ;
	DepthFirstSearch ( 1 );
	BuildRMQ();
	int Answer;
	for ( ; M > 0 ; --M )
	{
		Answer = Query ( X , Y );
		X = ( X * A + Y * B ) % N + 1 ;
		Y =  ( Y * C + Answer * D ) % N + 1;
		if ( M <= P ) out << Answer <<"\n";
	}
	in.close();
	out.close();
	return 0;
}