Pagini recente » Cod sursa (job #1964622) | Cod sursa (job #1184907) | Cod sursa (job #1220295) | Istoria paginii runda/tema_4/clasament | Cod sursa (job #1958592)
#include <fstream>
#include <vector>
using namespace std;
const int kLog = 18;
struct Node
{
int ancestors[kLog];
int anc_len = 0;
int exit_time;
int father_cost;
vector<int> edges;
};
using Tree = vector<Node>;
void Dfs(Tree &t, int node, vector<int> &st, int &nst)
{
static int time = 0;
++time;
st[nst++] = node;
if (nst != 1) {
int fa = st[nst - 2];
t[node].ancestors[0] = fa;
t[node].anc_len = 1;
for (int i = 1; (1 << i) < nst; ++i) {
t[node].ancestors[i] = t[fa].ancestors[i - 1];
fa = t[fa].ancestors[i - 1];
t[node].anc_len = i + 1;
}
}
for (const auto &son : t[node].edges) {
Dfs(t, son, st, nst);
}
t[node].exit_time = ++time;
--nst;
}
void FindAncestors(Tree &t, int root)
{
vector<int> st(t.size());
int nst = 0;
Dfs(t, root, st, nst);
}
int FindLca(const Tree &t, int x, int y)
{
if (x == y) {
return x;
}
if (t[x].exit_time > t[y].exit_time) {
swap(x, y);
}
int pos = 0;
int pow = (1 << 20);
while (pow > 0) {
if (pow + pos < t[x].anc_len) {
int fa = t[x].ancestors[pos + pow];
if (t[fa].exit_time < t[y].exit_time) {
pos += pow;
}
}
pow >>= 1;
}
return FindLca(t, y, t[x].ancestors[pos]);
}
int FindMin(const Tree &t, int x, int y)
{
int lca = FindLca(t, x, y);
int min_cost = (1 << 25);
while (x != lca) {
min_cost = min(min_cost, t[x].father_cost);
x = t[x].ancestors[0];
}
while (y != lca) {
min_cost = min(min_cost, t[y].father_cost);
y = t[y].ancestors[0];
}
return min_cost;
}
int main()
{
ifstream fin("atac.in");
ofstream fout("atac.out");
int n, q, p;
fin >> n >> q >> p;
Tree tree(n);
for (int i = 1; i < n; ++i) {
int fa, cost;
fin >> fa >> cost;
tree[i].father_cost = cost;
tree[fa - 1].edges.push_back(i);
}
FindAncestors(tree, 0);
int x, y, a, b, c, d;
fin >> x >> y >> a >> b >> c >> d;
for (int i = 1; i <= q + 1; ++i) {
int res = FindMin(tree, x - 1, y - 1);
if (q - i + 1 < p) {
fout << res << "\n";
}
int new_x = (x * a + y * b) % (n + 1);
int new_y = (y * c + res * d) % (n + 1);
x = new_x;
y = new_y;
}
return 0;
}