Cod sursa(job #1491075)

Utilizator DacianBocea Dacian Dacian Data 24 septembrie 2015 19:11:39
Problema Atac Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.44 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <iostream>

using namespace std;

const int INF = 1 << 30;
int M[17][32300], Str[17][32300],cost[16][32001], h[32001],v[120000], euler[120000], d[120000],depth[32001], N, R, P, o = 0, min1 = 120000,MD=0;
vector<pair<int, int>> g[36002];

void e(int current, int& i, int dist){
	euler[i] = current;
	d[i] = dist;
	depth[current] = dist;
	if (MD < dist) MD = dist;
	if (h[current] == -1)h[current] = i;
	for (auto& j : g[current]){
		Str[0][j.second] = current;
		cost[0][j.second] = j.first;
		++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]];
}

void BA() {
	for (int l = 1; (1 << l) <= MD; l += 1) {
		for (int i = 1; i <= N; i += 1) {
			Str[l][i] = Str[l - 1][Str[l - 1][i]];
			if (cost[l - 1][i]<cost[l - 1][Str[l - 1][i]])
				cost[l][i] = cost[l - 1][i];
			else cost[l][i] = cost[l - 1][Str[l - 1][i]];
		}
	}
}

int min2(int node, int anc) {
	int result = INF;
	for (int l = depth[node] - depth[anc]; l > 0; l -= (1 << v[l])) {
		result = result < cost[v[l]][node] ? result : cost[v[l]][node];
		node = Str[v[l]][node];
	}
	return result;
}


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));
	}
	f >> X >> Y >> a >> b >> c >> D;
	memset(h, -1, sizeof(h));
	for (int j = 0; (1 << j) <= N; ++j) {
		for (int i = 1; i <= N; ++i) {
			cost[j][i] = INF;
		}
	}
	e(1,o,1);
	rmq(); 
	for (int i = 2; i <= o; ++i)
		v[i] = 1 + v[i / 2]; 
	BA(); int LC, m1, m2;

	for (int i = 1; i <= R; ++i){
		if (X == Y) min1 = 0;
		else{
			LC = Lca(X, Y), m1 = min2(X, LC), m2 = min2(Y, LC);
			min1 = m1 < m2 ? m1 : m2;
		}
		if (R - P < i){
			of <<min1 << "\n";
		}
		X = (X*a + Y*b) % N + 1;
		Y = (Y*c + D*min1) % N + 1;
	}
}