Cod sursa(job #521801)

Utilizator cosmyoPaunel Cosmin cosmyo Data 13 ianuarie 2011 13:35:48
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <cstdio>
#include <vector>
#define mp make_pair
#define f first
#define s second
using namespace std;
const int N = 50005;
const int INF = 1000000000;
int nr, m, p ,n, v[N], P[2 * N], rmq[18][2 * N], A, B, C, D, X, Y, Z, c[N], ENTER[N], L[2 * N];
vector<int> a[N];

void dfs(int k ) {
	int i;
	P[++nr] = k;
	ENTER[k] = nr;
	v[k] = 1;
	for(i = 0; i < a[k].size(); ++i)
		if(!v[a[k][i]]) {
			dfs(a[k][i]);
			P[++nr] = k;
		}
}

void solve_rmq() {
	int i, j;
	L[1] = 0;
	for(i = 1; i <= n; ++i){
		L[i * 2] = L[i] + 1;
		L[i * 2 + 1] = L[i] + 1;
	}
	v[1] = INF;
	for(i = 2; i <= n; ++i)
		v[i] = c[i];
	for(i = 1; i <= nr; ++i)
		rmq[0][i] = P[i];
	int p = 1;
	for(i = 1; i <= L[nr]; ++i, p *= 2)
		for(j = 1; j <= (nr - 2 * p) + 1; ++j) {
			rmq[i][j] = rmq[i - 1][j];
			if(v[rmq[i][j]] > v[rmq[i - 1][j + p]])
				rmq[i][j] = rmq[i - 1][j + p];
		}
}

int RMQ(int x, int y) {
	int w = L[y - x + 1];
	int p = 1 << w;
	if(v[rmq[w][x]] < v[rmq[w][y - p + 1]])
		return v[rmq[w][x]];
		else
			return v[rmq[w][y - p + 1]];
}

int main() {
	freopen("atac.in", "r", stdin);
	freopen("atac.out", "w", stdout);
	int i, x ,y, j;
	scanf("%d %d %d", &n, &m, &p);
	for(i = 1; i < n; ++i)
		scanf("%d %d", &x, &y), 	a[i + 1].push_back(x),	a[x].push_back(i + 1),	c[i + 1] = y;
	dfs(1);
	scanf("%d %d %d %d %d %d", &X, &Y, &A, &B, &C, &D);
	solve_rmq();
	for(i = m; i >= 1; --i) {
		if(ENTER[X] <= ENTER[Y])
			Z = RMQ(ENTER[X], ENTER[Y]);
			else
			Z = RMQ(ENTER[Y], ENTER[X]);
		if(i <= p)
			printf("%d\n", Z);
		x = X;
		y = Y;
		X = (x * A + y * B) % n + 1;
		Y = (y * C + Z * D) % n + 1;
	}

	return 0;
}