Cod sursa(job #500726)

Utilizator andrey_porscheGraur Andrei andrey_porsche Data 12 noiembrie 2010 22:28:56
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

#define Nmax 100010
#define INF 1 << 30
 
int n, M, P, X, Y, Z, A, B, C, D, N;
int R[19][Nmax], Niv[Nmax], Poz[Nmax], Nod[Nmax], NIV[Nmax], lg[Nmax], S[19][Nmax], Cst[19][Nmax];
vector < pair <int, int> > V[Nmax];

void citire () {
	
	int i, tata, cst;
	
	scanf ("%d %d %d", &n, &M, &P);
	for (i = 2; i <= n; i++) {
		scanf ("%d %d", &tata, &cst);
		V[tata].push_back ( make_pair (i, cst) );
		S[0][i] = tata;
		Cst[0][i] = cst;
	}
	
	scanf ("%d %d %d %d %d %d", &X, &Y, &A, &B, &C, &D);
}

void dfs (int nod, int niv) {
	
	Nod[++N] = nod; Niv[N] = niv; R[0][N] = N; NIV[nod] = niv; Poz[nod] = N;
	
	for (vector < pair <int, int> >::iterator it = V[nod].begin (); it != V[nod].end (); it++) {
		dfs (it->first, niv + 1);
		Nod[++N] = nod; Niv[N] = niv; R[0][N] = N;
	}
}

void rmq () {
	
	int i, k;
	for (i = 2; i <= N; i++) 
		lg[i] = lg[i >> 1] + 1;
	
	for (k = 1; k <= lg[N]; k++) 
		for (i = 1; i + (1 << k) - 1 <= N; i++) 
			if ( Niv[ R[k-1][i] ] < Niv [ R[k - 1][ i + (1 << (k - 1)) ] ]) R[k][i] = R[k - 1][i];
			else R[k][i] = R[k - 1][i + ( 1 << (k - 1) )];
}


int LCA (int x, int y) {
	
	int len, aux;
	x = Poz[x], y = Poz[y];
	if (x > y) 
		aux = x, x = y, y = aux;
	
	len = lg[y - x];
	
	if (Niv[ R[len][x] ] < Niv[ R[len][y - (1 << len) + 1] ]) return Nod[ R[len][x] ];
	else return Nod[ R[len][y - (1 << len) + 1] ];
}

void rezolva () {
	
	int lca, dif, aX, aY;
	
	for (; M; M--) {
		aX = X, aY = Y;
		lca = LCA (X, Y);
		
		Z = INF;
		if (X == Y) Z = 0;
		
		while (X != lca) {
			dif = lg[NIV[X] -  NIV[lca]];
			Z = min (Z, Cst[dif][X]);
			X = S[dif][X];
		}
		
		while (Y != lca) {
			dif = lg[NIV[Y] - NIV[lca]];
			Z = min (Z, Cst[dif][Y]);
			Y = S[dif][Y];
		}
		
		if (M <= P) printf ("%d\n", Z);
		X = (aX * A + aY * B) % n + 1;
		Y = (aY * C + Z * D) % n + 1;
	}
}

void stramosi () {
	
	int k, i;
	
	for (k = 1; k <= lg[n]; k++) 
		for (i = 2; i <= n; i++)
			if (NIV[i] - 1 >= (1 << k))
				S[k][i] = S[k - 1][ S[k - 1][i] ];
	
	for (k = 1; k <= lg[n]; k++) 
		for (i = 2; i <= n; i++) 
			if (NIV[i] - 1 >= (1 << k)) 
				Cst[k][i] = min ( Cst[k - 1][i], Cst[k - 1][ S[k - 1][i] ] );
}

int main () {

	freopen ("atac.in", "r", stdin);
	freopen ("atac.out", "w", stdout);
	
	citire ();
	
	dfs (1, 1);
	rmq ();
	stramosi ();
	
	rezolva ();
	
	return 0;
}