Cod sursa(job #1046532)

Utilizator ELHoriaHoria Cretescu ELHoria Data 3 decembrie 2013 01:21:26
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream cin("atac.in");
ofstream cout("atac.out");

const int nmax = 1 << 15;
int N, M, P;
int A, B, C, D;
int X, Y;
vector<int> G[nmax];
int T[16][nmax];
int cost[16][nmax];
int lg[nmax];
int lvl[nmax];

void readData() {
	cin >> N >> M >> P;	
	for (int i = 2;i <= N;i++) {
		cin >> T[0][i] >> cost[0][i];
		G[i].push_back(T[0][i]);
		G[T[0][i]].push_back(i);
	}
	cin >> X >> Y >> A >> B >> C >> D;
}

void df(int v,int fn) {
	for (const int &w : G[v]) {
		if (w != fn) {
			lvl[w] = lvl[v] + 1;
			df(w,v);
		}
	}
}


void compute() {
	for (int i = 2;i <= N;i++) {
		lg[i] = lg[i >> 1] + 1;
	}
	cost[0][0] = cost[0][1] = int(1e9);
	for (int i = 1;(1 << i) <= N;i++) {
		for (int j = 1;j <= N;j++) {
			T[i][j] = T[i - 1][T[i - 1][j]];
			int x = j;
			for (int w = 0;w < i;w++) x = T[x][w];
			cost[i][j] = min(cost[i - 1][x],cost[i - 1][T[i - 1][j]]);
		}
	}
}

inline int getLca(int x,int y) {
	if (x == y) 
		return x;
	if (lvl[x] > lvl[y]) {
		while (lvl[x] > lvl[y]) {
			x = T[lg[lvl[x] - lvl[y]]][x];
		}
	} else 
	if (lvl[y] > lvl[x]) {
		while (lvl[y] > lvl[x]) {
			y = T[lg[lvl[y] - lvl[x]]][y];
		}
	}

	for(int l = lg[lvl[x]];l >= 0;l--) {
		if (T[l][x] != T[l][y]) {
			x = T[l][x];
			y = T[l][y];
		}
	}
	return T[0][x];
}

inline int query(int x,int y) {
	if (x == y) {
		return 0;
	}
	int lca = getLca(x,y);
	int d = lvl[x] - lvl[lca];
	int arr[] = {x,y};
	int ret = int(1e9);
	int l;
	for (int i = 0;i < 2;i++) {
		x = arr[i];
		d = lvl[x] - lvl[lca];
		while (d > 0) {
			l = lg[d];
			ret = min(ret,cost[l][x]);
			x = T[l][x];
			d -= (1 << l);
		}
		
	}
	return ret;
}


int main()
{
	readData();
	compute();
	df(1,0);
    for (int i = 1;i <= M;i++) {
		int Z = query(X,Y);
		X = (X * A + Y * B) % N + 1;
		Y = (Y * C + Z * D) % N + 1;
		if (i >= M - P + 1) {
			cout << Z << "\n";
		}
	}
	return 0;
}