Pagini recente » Cod sursa (job #1607696) | Cod sursa (job #262759) | Cod sursa (job #191910) | Cod sursa (job #355023) | Cod sursa (job #2311337)
#include <fstream>
#include <vector>
#include <algorithm>
#define sz size()
#define pb push_back
using namespace std ;
ifstream f ("atac.in") ;
ofstream g ("atac.out") ;
const int NR = 32001 ;
vector < pair < int , int > > v [ NR ] ;
int level [ NR ] , firstap [ NR ] , euler_edges [ 2 * NR ] , X , Y , A , B , C , D , Z , cnt , n , m , q , a [ 2 * NR ][ 15 ] , lg [ 2 * NR ] ;
void input ()
{
f >> n >> m >> q ;
for ( int i = 2 ; i <= n ; ++ i )
{
int x , y ; f >> x >> y ;
v [ i ].pb( make_pair( x , y ) ) ;
v [ x ].pb( make_pair( i , y ) ) ;
}
f >> X >> Y >> A >> B >> C >> D ;
firstap [ 1 ] = 1 ;
}
void euler_dfs ( int nod , int cost , int father )
{
level [ nod ] = level [ father ] + 1 ;
for( size_t i = 0 ; i < v [ nod ].sz ; ++ i )
{
if ( !level [ v [ nod ][ i ].first ] )
{
++ cnt ;
firstap [ v [ nod ][ i ].first ] = cnt + 1 ;
euler_edges [ cnt ] = v [ nod ][ i ].second ;
euler_dfs ( v [ nod ][ i ].first , v [ nod ][ i ].second , nod ) ;
}
}
euler_edges [ ++ cnt ] = cost ;
}
void rmq ()
{
cnt -- ;
int i , j ;
for ( i = 2 ; i <= cnt ; ++ i ) a [ i ][ 0 ] = euler_edges [ i ] , lg [ i ] = lg [ i >> 1 ] + 1 ;
for ( j = 1 ; j <= lg [ cnt ] ; ++ j )
for ( i = 1 ; i + ( 1 << j ) <= cnt + 1 ; ++ i )
a [ i ][ j ] = min ( a [ i ][ j - 1 ] , a [ i + ( 1 << ( j - 1 ) ) ][ j - 1 ] ) ;
}
void solve_tasks ()
{
for ( int i = 1 ; i <= m ; ++ i )
{
int st = firstap [ X ] ;
int dr = firstap [ Y ] - 1 ;
if ( dr < st ) swap ( dr , st ) ;
int interval = lg [ dr - st + 1 ] ;
Z = min ( a [ st ][ interval ] , a [ dr + 1 - ( 1 << interval ) ][ interval ] ) ;
if ( i >= q ) g << Z << "\n" ;
X = ( X * A + Y * B ) % n + 1 ;
Y = ( Y * C + Z * D ) % n + 1 ;
}}
int main ()
{
input() ;
euler_dfs( 1 , 0 , 0 ) ;
rmq() ;
solve_tasks() ;
return 0 ;
}