Cod sursa(job #521857)

Utilizator cosmyoPaunel Cosmin cosmyo Data 13 ianuarie 2011 16:29:59
Problema Atac Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 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 s[25][N], nr, m, p ,n, v[N], P[2 * N], rmq[25][2 * N], A, B, C, D, X, Y, Z, c[N], ENTER[N], L[2 * N], MIN[25][N];
vector<int> a[N], g[N];

void dfs(int k ) {
	int i;
	P[++nr] = k;
	ENTER[k] = nr;
	for(i = 0; i < a[k].size(); ++i)
		if(!v[a[k][i]]) {
			v[a[k][i]] = v[k]  + 1;
			s[0][a[k][i]] = k;
			MIN[0][a[k][i]] = c[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;
	}
	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 rmq[w][x];
		else
			return rmq[w][y - p + 1];
}

int askmin(int X, int Y) {
	int k = v[X] - v[Y];
	int min = INF, i;
	for(i = 20; i >= 0;  --i)
		if((1<<i) & k) {
			if(min > MIN[i][X])
				min = MIN[i][X];
			X = s[i][X];
		}
	return min;
}

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;
	v[1] = 1;
	dfs(1);
	scanf("%d %d %d %d %d %d", &X, &Y, &A, &B, &C, &D);
	solve_rmq();
	for(i = 1; i <= 20; ++i)
		for(j = 1; j <= n; ++j) {
			s[i][j] = s[i - 1][s[i - 1][j]];
			MIN[i][j] = min(MIN[i - 1][j], MIN[i - 1][s[i -1][j]]);
		}
	for(i = m; i >= 1; --i) {
		if(ENTER[X] <= ENTER[Y])
			Z = RMQ(ENTER[X], ENTER[Y]);
			else
			Z = RMQ(ENTER[Y], ENTER[X]);
			Z = min(askmin(X,Z), askmin(Y,Z));
		
		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;
}