Pagini recente » Cod sursa (job #1165610) | Cod sursa (job #926521) | Cod sursa (job #1959720) | Cod sursa (job #2365258) | Cod sursa (job #1536013)
#include <stdio.h>
#define MAX_N 32000
#define MAX_LOG 15
#define NIL -1
#define INF 0x3F3F3F3F
#define MIN(A, B) ((A) < (B) ? (A) : (B))
#define LOG2(X) (31 - __builtin_clz((X)))
typedef struct {
int v, next;
} cell;
cell l[MAX_N - 1];
int adj[MAX_N];
int anc[MAX_LOG][MAX_N];
int cost[MAX_LOG][MAX_N];
int depth[MAX_N];
void addEdge(int u, int v, int pos) {
l[pos].v = v;
l[pos].next = adj[u];
adj[u] = pos;
}
void DFS(int u) {
int i, v;
for ( i = adj[u]; i != NIL; i = l[i].next ) {
v = l[i].v;
depth[v] = depth[u] + 1;
DFS(v);
}
}
int main(void) {
FILE *fin, *fout;
int n, q, k, i, j;
int nQ;
int u, v, a, b, c, d;
int tmp;
fin = fopen( "atac.in", "r" );
fscanf( fin, "%d%d%d", &n, &q, &nQ );
for ( i = 0; i < n; i++ ) {
adj[i] = NIL;
}
for ( i = 1; i < n; i++ ) {
fscanf( fin, "%d%d", &anc[0][i], &cost[0][i] );
anc[0][i]--;
addEdge( anc[0][i], i, i - 1 );
}
fscanf( fin, "%d%d%d%d%d%d", &u, &v, &a, &b, &c, &d );
fclose( fin );
depth[0] = 1;
DFS( 0 );
for ( i = 1; (1 << i) <= n; i++ ) {
for ( j = 0; j < n; j++ ) {
cost[i][j] = MIN( cost[i][j], cost[i][ anc[i - 1][j] ] );
anc[i][j] = anc[i - 1][ anc[i - 1][j] ];
}
}
fout = fopen( "atac.out", "w" );
while ( q-- ) {
i = u; j = v;
u--; v--;
if ( depth[u] > depth[v] ) {
tmp = u;
u = v;
v = tmp;
}
tmp = 0;
if ( u != v ) {
tmp = INF;
for ( k = LOG2( depth[v] ); k >= 0; k-- ) {
if ( depth[v] - (1 << k) >= depth[u] ) {
tmp = MIN( tmp, cost[k][v] );
v = anc[k][v];
}
}
if ( u != v ) {
for ( k = LOG2( depth[u] ); k >= 0; k-- ) {
if ( anc[k][u] && anc[k][u] != anc[k][v] ) {
tmp = MIN( cost[k][u], tmp );
tmp = MIN( cost[k][v], tmp );
u = anc[k][u]; v = anc[k][v];
}
}
tmp = MIN( cost[0][u], tmp );
tmp = MIN( cost[0][v], tmp );
}
}
if ( q < nQ ) {
fprintf( fout, "%d\n", tmp );
}
u = ( i * a + j * b ) % n + 1;
v = ( j * c + tmp * d ) % n + 1;
}
fclose( fout );
return 0;
}