Pagini recente » Cod sursa (job #973751) | Cod sursa (job #2078767) | Cod sursa (job #78204) | Cod sursa (job #1578076) | Cod sursa (job #1481353)
#include<fstream>
#include<vector>
using namespace std;
ifstream fin( "atac.in" ); ofstream fout( "atac.out" );
const int nmax = 32000;
const int logmax = 15;
const int inf = 1 << 30;
int n, z;
int d[ logmax + 1 ][ nmax + 1 ];
int minval[ logmax + 1 ][ nmax + 1 ];
int h[ nmax + 1 ], tata[ nmax + 1 ];
struct muchie {
int y, cost;
muchie() {}
muchie( int _y, int _cost ) : y( _y ), cost( _cost ) {}
};
vector< muchie > g[ nmax + 1 ];
void dfs( int nod ) {
for( vector< muchie >::iterator it = g[ nod ].begin(); it != g[ nod ].end(); ++ it ) {
if ( (it -> y) != tata[ nod ] ) {
tata[ it -> y ] = nod;
h[ it -> y ] = h[ nod ] + 1;
minval[ 0 ][ it -> y ] = it -> cost;
dfs( it -> y );
}
}
}
inline int min2( int a, int b ) {
return ( a < b ? a : b );
}
void dinamicuta() {
for( int i = 1; i <= n; ++ i ) {
d[ 0 ][ i ] = tata[ i ];
}
for( int i = 1; (1 << i) <= n; ++ i ) {
for( int j = 1; j <= n; ++ j ) {
d[ i ][ j ] = d[ i - 1 ][ d[ i - 1 ][ j ] ];
minval[ i ][ j ] = min2( minval[ i - 1 ][ j ], minval[ i - 1 ][ d[ i - 1 ][ j ] ] );
}
}
}
void urcare( int &nod, int dist ) {
for( int i = 0; (1 << i) <= dist; ++ i ) {
if ( dist & (1 << i) ) {
z = min2( z, minval[ i ][ nod ] );
nod = d[ i ][ nod ];
}
}
}
void solve( int x, int y ) {
if ( x == y ) {
z = 0; return ;
}
z = inf;
if ( h[ x ] > h[ y ] ) {
urcare( x, h[ x ] - h[ y ] );
} else {
urcare( y, h[ y ] - h[ x ] );
}
int n2;
for( n2 = 1; (1 << n2) <= n; ++ n2 ) {
}
for( int step = n2; step >= 0; step -- ) {
if ( d[ step ][ x ] != d[ step ][ y ] ) {
z = min2( min2( z, minval[ step ][ x ] ), minval[ step ][ y ] );
x = d[ step ][ x ];
y = d[ step ][ y ];
}
}
if ( x != y ) {
z = min2( minval[ 0 ][ x ], minval[ 0 ][ y ] );
}
}
int main() {
int m, p;
fin >> n >> m >> p;
for( int i = 2; i <= n; ++ i ) {
int x, y;
fin >> x >> y;
g[ i ].push_back( muchie( x, y ) );
g[ x ].push_back( muchie( i, y ) );
}
dfs( 1 );
dinamicuta();
int x, y, a, b, c, d;
fin >> x >> y >> a >> b >> c >> d;
for( int i = 0; i < m; ++ i ) {
solve( x, y );
if ( m - p <= i ) {
fout << z << "\n";
}
int xi, yi;
xi = ( x * a + y * b ) % n + 1;
yi = ( y * c + z * d ) % n + 1;
x = xi;
y = yi;
}
fin.close();
fout.close();
return 0;
}