Pagini recente » Cod sursa (job #2287654) | Cod sursa (job #475977) | Cod sursa (job #324799) | Cod sursa (job #2888936) | Cod sursa (job #1033381)
#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[20];
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;
}