Cod sursa(job #1523588)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 12 noiembrie 2015 21:13:11
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>

#define infile "atac.in"
#define outfile "atac.out"

using namespace std;

struct Node {
	
	int node;
	int level;

	Node() {}
	Node(int node, int level) {
		this->node = node;
		this->level = level;
	}

	bool operator < (const Node &x) const {
		return x.level > level;
	}
};

int n;
int parent[17][33000], cost[17][33000], firstAp[33000], mostSignifBit[100005], _level[33000];

vector<Node> rmq[17];
vector<int> graph[33000];

void dfs(int node, int level) {

	rmq[0].push_back(Node(node, level));
	firstAp[node] = rmq[0].size() - 1;
	_level[node] = level;

	for (int adj : graph[node]) {

		dfs(adj, level + 1);
		rmq[0].push_back(Node(node, level));

	}

}

void calcRmq(void) {

	for (int i = 1; (1 << i) <= (int)rmq[0].size() - 1; ++i) {

		rmq[i].resize(rmq[0].size());

		for (int j = 1; j <= (int)rmq[0].size() - 1 - (1 << i) + 1; ++j) {

			rmq[i][j] = min(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);

		}

	}

}

void calcMostSignifBit(void) {

	mostSignifBit[1] = 0;

	for (int i = 2; i <= 100000; ++i)
		mostSignifBit[i] = mostSignifBit[i / 2] + 1;

}

void calcCost(void) {

	for (int i = 1; (1 << i) <= n; ++i) {

		for (int j = 1; j <= n; ++j) {

			cost[i][j] = min(cost[i - 1][j], cost[i - 1][parent[i - 1][j]]);
			parent[i][j] = parent[i - 1][parent[i - 1][j]];

		}

	}

}

int getLca(int x, int y) {

	x = firstAp[x];
	y = firstAp[y];

	if (x > y)
		swap(x, y);

	int pow = mostSignifBit[y - x + 1];

	if (rmq[pow][x] < rmq[pow][y - (1 << pow) + 1])
		return rmq[pow][x].node;
	else
		return rmq[pow][y - (1 << pow) + 1].node;

}

int getCost(int x, int y) {

	if (x == y)
		return 2000000000;

	int pow = mostSignifBit[_level[x] - _level[y]];

	return min(cost[pow][x], getCost(parent[pow][x], y));

}

int main() {

	ifstream fin(infile);
	ofstream fout(outfile);

	int m, p;
	fin >> n >> m >> p;

	for (int i = 2; i <= n; ++i) {

		fin >> parent[0][i] >> cost[0][i];

		graph[parent[0][i]].push_back(i);

	}

	rmq[0].resize(1);
	
	dfs(1, 1);
	calcRmq();
	calcMostSignifBit();
	calcCost();

	int node1, node2, A, B, C, D;

	fin >> node1 >> node2 >> A >> B >> C >> D;

	for (int i = 1; i <= m; ++i) {

		int lca = getLca(node1, node2);

		int sol = 0;

		if (node1 != node2) {

			sol = min(getCost(node1, lca), getCost(node2, lca));

		}

		if (m - i + 1 <= p)
			fout << sol << '\n';

		node1 = (node1 * A + node2 * B) % n + 1;
		node2 = (node2 * C + sol * D) % n + 1;

	}

	return 0;

}

//Trust me, I'm the Doctor!