Pagini recente » Cod sursa (job #1828661) | Cod sursa (job #433898) | Cod sursa (job #1968376) | Cod sursa (job #591097) | Cod sursa (job #1523588)
#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!