Pagini recente » Cod sursa (job #1630116) | Cod sursa (job #1020779) | Cod sursa (job #1420426) | Cod sursa (job #2679715) | Cod sursa (job #2677806)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin( "atac.in" );
ofstream fout( "atac.out" );
const int MaxM = 500001;
const int MaxN = 32002;
const int MaxLog = 16;
struct edge {
int node, cost;
};
vector<edge> G[MaxN];
int anc[MaxN][MaxLog];
int mn[MaxN][MaxLog];
int log[MaxN];
int level[MaxN], vis[MaxN];
void DFS( int node ) {
vis[node] = 1;
for ( int i = 0; i < (int)G[node].size(); ++i ) {
if ( !vis[G[node][i].node] ) {
level[G[node][i].node] = level[node] + 1; //actualizam nivelul
anc[G[node][i].node][0] = node; //parintele lui G[node][i].node este node
mn[G[node][i].node][0] = G[node][i].cost; //minimul este chiar costul muchiei dintre ei
DFS( G[node][i].node ); //ne extindem la urmatorul
}
}
}
int query( int x, int y ) {
int sol = 1e9, lg;
if ( level[x] < level[y] ) { //vrem ca level[x] > level[y] pentru a evita if-uri
swap( x, y );
}
while ( level[x] != level[y] ) {
lg = log[level[x] - level[y]]; //luam puterea maxima de 2 care intra in diferenta de nivel
sol = min( sol, mn[x][lg] ); //actualizam si minimul
x = anc[x][lg]; //x va deveni stramosul 2^lg al lui
}
lg = MaxLog - 1;
while ( x != y ) {
while ( lg && anc[x][lg] == anc[y][lg] ) {
lg >>= 1;
}
sol = min({ sol, mn[x][lg], mn[y][lg] });
x = anc[x][lg];
y = anc[y][lg];
}
if ( sol == 1e9 ) {
sol = 0;
}
return sol;
}
int q[MaxM];
int main() {
int n, m, p, x, y, a, b, c, d, res, r;
edge e;
fin >> n >> m >> p;
for ( int i = 2; i <= n; ++i ) {
fin >> e.node >> e.cost;
G[i].push_back( e );
G[e.node].push_back( { i, e.cost } );
}
level[1] = 0;
DFS( 1 );
for ( int k = 1; k <= MaxLog - 1; ++k ) {
for ( int i = 1; i <= n; ++i ) {
anc[i][k] = anc[anc[i][k - 1]][k - 1];
mn[i][k] = min( mn[i][k - 1], mn[anc[i][k - 1]][k - 1] );
}
}
for ( int i = 2; i <= n; ++i ) {
log[i] = log[i / 2] + 1;
}
fin >> x >> y >> a >> b >> c >> d;
r = 0;
for ( int i = 0; i < m; ++i ) {
res = query( x, y );
q[r++] = res;
x = (x * a + y * b) % n + 1;
y = (y * c + res * d) % n + 1;
}
for ( int i = r - p; i < r; ++i ) {
fout << q[i] << "\n";
}
fin.close();
fout.close();
return 0;
}