Pagini recente » Cod sursa (job #167139) | Cod sursa (job #1894365) | Cod sursa (job #1527750) | Cod sursa (job #2851971) | Cod sursa (job #2311352)
#include <fstream>
#include <iostream>
#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 firstap [ NR ] , euler_edges [ 2 * NR ] , X , Y , A , B , C , D , Z , cnt , n , m , q , a [ 2 * NR ][ 15 ] , lg [ 2 * NR ] ;
bool viz [ 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 ){
viz [ nod ] = true ;
for( size_t i = 0 ; i < v [ nod ].sz ; ++ i ){
if ( !viz [ 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 ;
a [ 1 ][ 0 ] = euler_edges [ 1 ] ;
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 ){
if ( X == Y ) Z = 0 ;
else
{int st = firstap [ X ] ;
int dr = firstap [ Y ] ;
if ( dr < st ) swap ( dr , st ) ;
dr -- ;
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 ;}