Pagini recente » Cod sursa (job #2128675) | Istoria paginii runda/antrenament_oji2020/clasament | Cod sursa (job #2507054) | Cod sursa (job #1222268) | Cod sursa (job #1958621)
#include <fstream>
#include <vector>
using namespace std;
const int kLog = 20;
struct Node
{
int ancestors[kLog];
int anc_len = 0;
int exit_time;
int father_cost;
vector<int> edges;
};
using Tree = vector<Node>;
int time = 0;
void Dfs(Tree &t, int node, vector<int> &st, int &nst)
{
++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; ++i) {
int res = ((x == y) ? 0 : FindMin(tree, x - 1, y - 1));
// fout << x << " " << y << "\n";
// fout << "lca = " << FindLca(tree, x - 1, y - 1) + 1 << "\n";
if (q - i <= 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;
}