Pagini recente » Cod sursa (job #1054536) | Cod sursa (job #3172627) | Download-uri | Cod sursa (job #1515327) | Cod sursa (job #2648125)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int NMAX = 32000;
const int LOGNMAX = 15;
const int INF = 1e9 + 1;
int RMQ[LOGNMAX + 1][2 * NMAX][2];
int log[2 * NMAX + 1];
int codification[NMAX];
int decodification[NMAX];
int first_appearance[NMAX];
struct edge {
int children;
int value;
};
vector <edge> edges[NMAX + 1];
int index, new_node;
void first_row( int current_node ) { /// first_row( 0, INF );
codification[current_node] = new_node;
decodification[new_node] = current_node;
RMQ[0][index][0] = new_node;
new_node ++;
index ++;
for ( auto x : edges[current_node] ) {
RMQ[0][index][1] = x.value;
first_row( x.children );
RMQ[0][index][1] = x.value;
RMQ[0][index++][0] = current_node;
}
}
void calculate_log( int n ) {
for ( int i = 2; i <= 2 * n; i ++ ) {
log[i] = log[i / 2] + 1;
}
}
void build_RMQ( int n ) {
int i, j, x;
for ( i = 1; ( 1 << i ) <= 2 * n - 1; i ++ ) {
for ( j = 0; j + ( 1 << i ) < 2 * n; j ++ ) {
RMQ[i][j][1] = min( RMQ[i - 1][j][1], RMQ[i - 1][j + ( 1 << ( i - 1 ) )][1] );
}
}
}
int ans( int i, int j, int x ) {
return ( min( RMQ[log[j - i + 1]][i][x], RMQ[log[j - i + 1]][j - ( 1 << ( log[j - i + 1] ) ) + 1][x] ) );
}
void calculate_appearances( int n ) {
int i;
for ( i = 0; i < n; i ++ )
first_appearance[i] = -1;
for ( i = 0; i < 2 * n - 1; i ++ ) {
if ( first_appearance[decodification[RMQ[0][i][0]]] == -1 )
first_appearance[decodification[RMQ[0][i][0]]] = i;
}
}
int main() {
ifstream fin( "atac.in" );
ofstream fout( "atac.out" );
int n, m, p, i, j, x, y, node, val, a, b, c, d, length, st, dr, answer;
fin >> n >> m >> p;
for ( i = 0; i < n - 1; i ++ ) {
fin >> node >> val;
edges[node - 1].push_back( { i + 1, val } );
}
calculate_log( n );
first_row( 0 );
RMQ[0][0][1] = INF;
build_RMQ( n );
// for ( i = 0; ( 1 << i ) <= 2 * n - 1; i ++ ) {
// for ( j = 0; j + ( 1 << i ) < 2 * n; j ++ ) {
// cout << RMQ[i][j][1] << ' ';
// }
// cout << endl;
// }
calculate_appearances( n );
fin >> x >> y >> a >> b >> c >> d;
for ( i = 0; i < m; i ++ ) {
st = first_appearance[codification[x - 1]];
dr = first_appearance[codification[y - 1]];
if ( st > dr )
swap( dr, st );
if ( dr == st )
answer = 0;
else
answer = ans( st, dr, 1 );
if ( i >= m - p )
fout << answer << '\n';
x = ( x * a + y * b ) % n + 1;
y = ( y * c + answer * d ) % n + 1;
}
return 0;
}