Cod sursa(job #220378)

Utilizator savimSerban Andrei Stan savim Data 10 noiembrie 2008 17:26:58
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.82 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define MAX_L 32010

int fol[MAX_L], tata[MAX_L], nivel[MAX_L];
int n, m, i, j, k, x , y, l, val, p , q, nr, X, Y, Z, A, B, C, D;
int euler[2 * MAX_L], adanc[2 * MAX_L];
int ap[MAX_L][2];
int rmq[MAX_L][25], str[MAX_L][25], Min[MAX_L][25];

vector <int> a[MAX_L], c[MAX_L];

void cit() {
	freopen("atac.in", "r", stdin);
	freopen("atac.out", "w", stdout);
	
	scanf("%d %d %d", &n, &m, &nr);
	for (i = 1; i < n; i++) {
		scanf("%d %d", &x, &y);
		a[x].push_back(i + 1); c[x].push_back(y);
		a[i + 1].push_back(x); c[i + 1].push_back(y);
	}
	scanf("%d %d %d %d %d %d", &X, &Y, &A, &B, &C, &D);
}

void dfs(int w, int nr) {
	euler[++k] = w; adanc[k] = nr;
	nivel[w] = nr;
	
	int l = a[w].size();
	for (int i = 0; i < l; i++)
		if (fol[a[w][i]] == 0) {
			Min[a[w][i]][0] = c[w][i];
			fol[a[w][i]] = 1; tata[a[w][i]] = w;
			
			dfs(a[w][i], nr + 1);
			
			fol[a[w][i]] = 0;
			euler[++k] = w; adanc[k] = nr;
		}
}

void solve() {
	fol[1] = 1;
	dfs(1,1);

	for (i = 1; i <= k; i++) {
		if (ap[euler[i]][0] == 0) ap[euler[i]][0] = i;
		ap[euler[i]][1] = i;
		rmq[i][0] = adanc[i];
	}
	
	for (j = 1; (1 << j) <= k; j++)
		for (i = 1; i <= k; i++) {
			rmq[i][j] = rmq[i][j - 1]; 
			if (i + (1 << (j - 1)) <= k && rmq[i][j] > rmq[i + (1 << (j - 1))][j - 1]) 
				rmq[i][j] = rmq[i + (1 << (j - 1))][j - 1]; 
		}
	
	//calculez al 1 << k - lea stramos al unui nod
	for (i = 1; i <= n; i++) str[i][0] = tata[i];
	for (j = 1; j <= 20; j++) {  
        for (i = 1; i <= n; i++)  
            str[i][j] = str[str[i][j - 1]][j - 1];
    }
	
	//calculez minimul pe intervalul i..i + 1<<k
	for (j = 1; (1 << j) <= n; j++) {
		for (i = 1; i <= n; i++) {
			Min[i][j] = Min[i][j - 1];
			if (nivel[i] - (1 << j) > 0) 
				Min[i][j] = min(Min[i][j - 1], Min[str[i][j - 1]][j - 1]);
		}
	}
}

int minim(int nod, int niv) {
	int p2 = 20, curent = (1 << 31) - 1;
	int k = nivel[nod], x = nod;
	
	while (k > niv && p2) {
		while (k - (1 << p2) <= niv && p2) p2--;
		curent = min(curent, Min[x][p2]);
		x = str[x][p2];
		k = nivel[x];
	}
	
	return curent;
}

void write() {
	for (i = 1; i <= m; i++) {
		if (X != Y)	{
			if (ap[X][0] < ap[Y][0]) p = ap[X][0];
			else p = ap[Y][0];
			if (ap[X][1] > ap[Y][1]) q = ap[X][1];
			else q = ap[Y][1];
		
			for (j = 0; j <= 20; j++)
				if (p + (1 << j) > q) break;
			j--;
			
			if (rmq[p][j] <= rmq[q - (1 << j)][j]) val = rmq[p][j];
			else val = rmq[q - (1 << j)][j];
			
			//lca -ul intre nodurile X si Y se va afla la adancimea val
			Z = min(minim(X, val), minim(Y, val));
		}
		else Z = 0;
		
		if (m - nr < i) printf("%d\n",Z);
		X = ((long long) X*A + Y*B) % n + 1;
		Y = ((long long) Y*C + Z*D) % n + 1;
	}
}

int main() {

	cit();
	solve();
	write();
	
	return 0;
}