Cod sursa(job #1046538)

Utilizator ELHoriaHoria Cretescu ELHoria Data 3 decembrie 2013 01:49:11
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 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(const int &v,int fn) {
	
	for (int i = 1;i <= lg[lvl[v]];i++) {
		T[i][v] = T[i - 1][T[i - 1][v]];
		cost[i][v] = min(cost[i - 1][v],cost[i - 1][T[i - 1][v]]);
	}

	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;
	}
}

inline int query(int x,int y) {
	if (x == y)  return 0;
	int ret = int(2e9);
	while (lvl[x] > lvl[y]) {
		ret = min(ret,cost[lvl[x] - lvl[y]][x]);
		x = T[lg[lvl[x] - lvl[y]]][x];
	}
	while (lvl[y] > lvl[x]) {
		ret = min(ret,cost[lvl[y] - lvl[x]][y]);
		y = T[lg[lvl[y] - lvl[x]]][y];
	}

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

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;
}