Cod sursa(job #1491031)

Utilizator DacianBocea Dacian Dacian Data 24 septembrie 2015 17:44:40
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

int M[15][32001], h[32001], euler[64002], v[64002], d[64002], N, R, P, o = 0, min1 = 100.000;
vector<pair<int, int>> g[36002], parrent[36002];

void e(int current, int& i, int dist){
	euler[i] = current;
	d[i] = dist;
	if (h[current] == -1)h[current] = i;
	for (auto& j : g[current]){
		++i;
		e(j.second, i, dist + 1);
		++i;
		euler[i] = current;
		d[i] = dist;
	}
}

void rmq(){
	for (int i = 0; i < o; ++i) M[0][i] = i;
	for (int j = 1; 1 << j <= o;++j)
		for (int i = 0; i + (1 << j) - 1 < o; ++i)
			if (d[M[j - 1][i]] < d[M[j - 1][i + (1 << (j - 1))]])
				M[j][i] = M[j - 1][i];
			else M[j][i] = M[j - 1][i + (1 << (j - 1))];
}

int Lca(int a, int b){
	int p1 = h[a], p2 = h[b];
	if (p2 < p1){
		p1 ^= p2; p2 ^= p1; p1 ^= p2;
	}
	int k = 0, p = 1;
	while (p <= p2 - p1 + 1){ p <<= 1; ++k; }
	--k;
	p >>= 1;
	return euler[d[M[k][p1]] <= d[M[k][p2 - (1 << k) + 1]] ? M[k][p1] : M[k][p2 - (1 << k) + 1]];
}

int min2(int b, int c){
	int rc = parrent[b][0].first;
	while (b != c){
		if (parrent[b][0].first < rc) rc = parrent[b][0].first;
		b = parrent[b][0].second;
	}
	return rc;
}

int main(){
	ifstream f("atac.in");
	ofstream of("atac.out");
	int a, b,c,D,X,Y;
	f >> N >> R >> P;
	for (int i = 2; i <= N; ++i){
		f >> a >> b;
		g[a].push_back(make_pair(b , i));
		parrent[i].push_back(make_pair(b, a));
	}
	f >> X >> Y >> a >> b >> c >> D;
	memset(h, -1, sizeof(h));
	e(1,o,0);
	rmq(); int k = 0;
	for (int i = 1; i <= R; ++i){
		++k;
		int LC = Lca(X, Y), m1 = min2(X, LC), m2 = min2(Y, LC);
		min1 = m1 < m2 ? m1 : m2;
		if (R - k+1 <= P)
			if (X == Y)of << "0\n"; 
			else of << min1 << "\n";
		X = (X*a + Y*b) % N + 1;
		Y = (Y*c + D*min1) % N + 1;
	}
}