Cod sursa(job #566153)

Utilizator Addy.Adrian Draghici Addy. Data 28 martie 2011 18:24:58
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define NMAX 32768
#define LOG 18

int R[LOG + 1][NMAX << 1], E[NMAX << 1], L[NMAX << 1], log[NMAX << 1], viz[NMAX << 1], S[LOG][NMAX], D[LOG][NMAX], F[NMAX], n, m, p, k, t, i, a, b, c, d, x, y, z;
vector <int> G[NMAX];

int lca (int, int), query (int, int), stramos (int, int);
void rmq (), dinamica (), stramosi (), euler (int, int);

int main () {
	
	freopen ("atac.in", "r", stdin);
	freopen ("atac.out", "w", stdout);
	
	scanf ("%d %d %d", &n, &m, &p);
	
	for (i = 2; i <= n; i++) {
		scanf ("%d %d", &t, &c);
		
		G[t].push_back (i);
		G[i].push_back (t);
		
		S[0][i] = t, D[0][i] = c;
	}
	
	euler (1, 0);
	
	rmq ();
	
	stramosi ();
	
	dinamica ();
	
	scanf ("%d %d %d %d %d %d", &x, &y, &a, &b, &c, &d);
	
	for (i = 1; i <= m; i++) {
		
		t = lca (x, y);
		
		if (t == x && t == y) z = 0;
		else if (t == x) z = query (L[ F[y] ] - L[ F[t] ], y);
		else if (t == y) z = query (L[ F[x] ] - L[ F[t] ], x);
		else z = min (query (L[ F[x] ] - L[ F[t] ], x), query (L[ F[y] ] - L[ F[t] ], y));
		
		if (i > m - p) printf ("%d\n", z);
		
		x = (x * a + y * b) % n + 1;
		y = (y * c + z * d) % n + 1;
	}
	
	return 0;
}

int query (int j, int i) {
	
	int k = log[j];
	
	if ((1 << k) == j) return D[k][i];
	
	return min (D[k][i], query (j - (1 << k), stramos ((1 << k), i)));
}

int stramos (int p, int q) {
	
	if (p == 0) return q;
	
	int k = log[p];
	
	return stramos (p - (1 << k), S[k][q]);
}

void dinamica () {
	
	for (int j = 1; (1 << j) <= n; j++)
		for (int i = 1; i <= n; i++) {
			int k = stramos ((1 << (j-1)), i);
			D[j][i] = min (D[j-1][i], D[j-1][k]);
		}
}

void stramosi () {
	
	for (int j = 1; (1 << j) <= n; j++)
		for (int i = 1; i <= n; i++)
			S[j][i] = S[j-1][ S[j-1][i] ];
}

void euler (int nod, int lev) {
	
	viz[nod] = 1;
	
	E[++k] = nod, L[k] = lev, F[nod] = k;
	for (vector <int>::iterator it = G[nod].begin (); it != G[nod].end (); it++)
		if (!viz[*it]) {
			euler (*it, lev + 1);
			E[++k] = nod, L[k] = lev;
		}
}

void rmq () {
	
	int i, j;
	
	for (i = 1; i <= k; i++) {
		R[0][i] = i;
		if (i > 1) log[i] = log[i >> 1] + 1;
	}
	
	for (j = 1; (1 << j) <= k; j++)
		for (i = 1; i + (1 << j) - 1 <= k; i++)
			if (L[ R[j-1][i] ] < L[ R[j-1][i + (1 << (j - 1))] ])
				R[j][i] = R[j-1][i];
			else
				R[j][i] = R[j-1][i + (1 << (j - 1))];
}

int lca (int x, int y) {
	
	int a = F[x], b = F[y], k, sol;
	
	if (a > b) swap (a, b);
	
	k = log[b - a + 1];
	
	if (L[ R[k][a] ] < L[ R[k][b - (1 << k) + 1] ])
		sol = R[k][a];
	else
		sol = R[k][b - (1 << k) + 1];
	
	return E[sol];
}