Pagini recente » Cod sursa (job #2932082) | Cod sursa (job #1325890) | Cod sursa (job #938354) | Cod sursa (job #3196947) | Cod sursa (job #1934871)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
const int N = 32010;
const int LOGN = 16;
const int INF = 1e8 ;
using namespace std;
int noNodes, noQueries , noAnswers;
vector <pair < int , int > > edges [ N ];
int viz[ N ];
int height [ N ] ;
int anchestor[ N ][ LOGN ] , bestEdge [ N ][ LOGN ];
void ComputeMat( int node ){
static int i ;
for ( i = 1 ; ( 1<<i ) <= height [ node ] ; i++ ){
anchestor [ node ][ i ] = anchestor [ anchestor [ node ][ i - 1 ] ][ i - 1 ] ;
bestEdge [ node ][ i ] = min ( bestEdge [ node ][ i - 1 ] , bestEdge [ anchestor [ node ][ i - 1 ] ][ i - 1 ] ) ;
}
}
void dfs ( int node ){
vector <pair < int , int > >::iterator it ;
int vec ;
viz [ node ] = 1 ;
for ( it = edges[ node ].begin() ; it != edges[ node ].end() ; it++ ){
vec = it->first ;
if ( viz [ vec ] ){
continue;
}
anchestor [ vec ] [ 0 ] = node ;
bestEdge [ vec ] [ 0 ] = it->second ;
height [ vec ] = height [ node ] + 1 ;
ComputeMat( vec );
dfs( vec );
}
}
int SolveQuery( int x , int y ){
static int diff , bestMuc ,i;
if ( height [ x ] < height [ y ] ){
int temp = x;
x = y ;
y = temp ;
}
bestMuc = INF ;
diff = height [ x ]- height [ y ];
for ( i = LOGN ; i >= 0 ; i -- )
if ( ( 1<<i ) <= diff ){
bestMuc = min ( bestMuc , bestEdge [ x ][ i ] );
x = anchestor [ x ] [ i ] ;
diff -= 1<<i ;
}
if ( x == y ){
return bestMuc ;
}
for ( i = LOGN ; i>=0 ; i-- ){
if ( anchestor [ x ] [ i ] == anchestor [ y ][ i ] || ( 1<<i ) >= height[ x ] ){
continue;
}
bestMuc = min ( bestMuc , bestEdge[ x ] [ i ] );
bestMuc = min ( bestMuc , bestEdge[ y ] [ i ] );
x = anchestor [ x ][ i ] ;
y = anchestor [ y ][ i ] ;
}
bestMuc = min( bestMuc , bestEdge [ x ][ 0 ] );
bestMuc = min( bestMuc , bestEdge [ y ][ 0 ] );
return bestMuc ;
}
int main(){
int i ;
freopen("atac.in","r",stdin);
freopen("atac.out","w",stdout);
scanf("%d%d%d",&noNodes, &noQueries , &noAnswers );
int x , y , cost ;
for ( i = 2 ; i <= noNodes ; i ++ ){
scanf("%d%d",&x , &cost);
edges [ x ].push_back( make_pair( i ,cost ) );
edges [ i ].push_back( make_pair( x ,cost ) );
}
dfs( 1 );
int A , B , C , D , sol;
scanf("%d%d%d%d%d%d",&x,&y,&A,&B,&C,&D);
for ( i = 0 ; i < noQueries ; i++ ){
sol = SolveQuery( x , y );
if ( i >= noQueries - noAnswers ){
printf("%d\n",sol);
}
x = ( x * A + y * B )% noNodes + 1;
y = ( y * C + sol * D )% noNodes + 1;
}
return 0;
}