Pagini recente » Cod sursa (job #2406068) | Cod sursa (job #1596599) | Cod sursa (job #1093992) | Cod sursa (job #1767808) | Cod sursa (job #2648310)
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
const int NMAX = 32000;
const int LOGNMAX = 15;
const int INF = 1e9 + 1;
struct edge {
int children;
int value;
};
vector <edge> edges[NMAX];
edge father[NMAX];
int ancestor[NMAX][LOGNMAX + 2];
int length[NMAX][LOGNMAX + 2];
int level[NMAX];
void init( int n ) {
int i, j;
for ( i = 0; i < n; i ++ ) {
for ( j = 0; j < LOGNMAX + 2; j ++ ) {
ancestor[i][j] = -1;
length[i][j] = -1;
}
}
}
void calculate_ancestors( int node, int lvl ) {
level[node] = lvl;
if ( node != 0 ) { /// != root
int i;
length[node][0] = father[node].value;
ancestor[node][0] = father[node].children;
i = 1;
while ( ancestor[ancestor[node][i - 1]][i - 1] != -1 ) {
ancestor[node][i] = ancestor[ancestor[node][i - 1]][i - 1];
length[node][i] = min( length[node][i - 1], length[ancestor[node][i - 1]][i - 1] );
i ++;
}
}
for ( auto& x : edges[node] ) {
calculate_ancestors( x.children, lvl + 1 );
}
}
int same_level( int& node, int lvl ) {
int minim, i;
i = LOGNMAX + 1;
minim = INF;
while ( level[node] != lvl ) {
while ( ancestor[node][i] == -1 || level[ancestor[node][i]] < lvl ) {
i --;
}
minim = min( minim, length[node][i] );
node = ancestor[node][i];
}
return minim;
}
int lca( int node1, int node2, int minim ) {
int i, ok = 0;
i = LOGNMAX + 1;
while ( i >= 0 ) {
while ( i >= 0 && ( ancestor[node1][i] == ancestor[node2][i] ) ) {
i --;
}
if ( i == -1 ) {
i = 0;
ok = 1;
}
minim = min( min( minim, length[node1][i] ), length[node2][i] );
node1 = ancestor[node1][i];
node2 = ancestor[node2][i];
i -= ok;
}
///cout << endl;
return minim;
}
int main() {
ifstream fin( "atac.in" );
ofstream fout( "atac.out" );
int n, m, p, i, j, x, y, node, val, a, b, c, d, st, dr, minim;
fin >> n >> m >> p;
for ( i = 0; i < n - 1; i ++ ) {
fin >> node >> val;
edges[node - 1].push_back( { i + 1, val } );
father[i + 1] = { node - 1, val };
}
init( n );
calculate_ancestors( 0, 0 );
fin >> x >> y >> a >> b >> c >> d;
for ( i = 0; i < m; i ++ ) {
st = x - 1;
dr = y - 1;
if ( dr == st )
minim = 0;
else {
if ( level[dr] > level[st] )
swap( st, dr );
minim = same_level( st, level[dr] );
minim = lca( st, dr, minim );
}
if ( i >= m - p ) {
fout << minim << '\n';
}
x = ( x * a + y * b ) % n + 1;
y = ( y * c + minim * d ) % n + 1;
}
return 0;
}