Pagini recente » Cod sursa (job #2707096) | Cod sursa (job #2359283) | Cod sursa (job #2507019) | Cod sursa (job #537271) | Cod sursa (job #2333155)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("atac.in");
ofstream fo("atac.out");
const int NMAX = 35000;
const int LOG = 20;
int n, m, pp;
vector < pair<int, int> > G[NMAX];
int h[NMAX], p[NMAX];
int sus[LOG][NMAX];
int minim[LOG][NMAX];
int prima[NMAX];
void dfs(int nod)
{
for (auto v: G[nod])
if (v.first != p[nod])
{
p[v.first] = nod;
prima[v.first] = v.second;
h[v.first] = h[nod] + 1;
dfs(v.first);
}
}
void precalcLca()
{
for (int i = 1; i <= n; i++)
sus[0][i] = p[i];
sus[0][1] = -1;
for (int i = 1; i < LOG; i++)
for (int j = 1; j <= n; j++)
sus[i][j] = sus[i - 1][sus[i - 1][j]];
}
int lca(int a, int b)
{
if (h[a] < h[b])
swap(a, b);
for (int i = LOG - 1; i >= 0; i--)
if (h[a] - (1 << i) >= h[b])
a = sus[i][a];
for (int i = LOG - 1; i >= 0; i--)
if (h[a] - (1 << i) >= 1 && sus[i][a] != sus[i][b])
a = sus[i][a], b = sus[i][b];
return p[a];
}
void precalcMinim() //
{
for (int i = 2; i <= n; i++)
minim[0][i] = prima[i];
minim[0][1] = 1000000;
for (int i = 1; i < LOG; i++)
for (int j = 1; j <= n; j++)
if (h[j] - (1 << i) >= 1)
minim[i][j] = min(minim[i - 1][j], minim[i - 1][sus[i - 1][j]]);
}
int getminim(int a, int b) // minimul pe drumul dintre a si b (b este stramos al lui a)
{
if (h[a] < h[b])
swap(a, b);
int ret = 1000000;
for (int i = LOG - 1; i >= 0; i--)
if (h[a] - (1 << i) >= h[b])
{
ret = min(ret, minim[i][a]);
a = sus[i][a];
}
return ret;
}
int main()
{
fi >> n >> m >> pp;
for (int i = 2; i <= n; i++)
{
int v, c;
fi >> v >> c;
G[i].push_back({v, c});
G[v].push_back({i, c});
}
h[1] = 1; dfs(1);
precalcLca();
precalcMinim();
int x, y, a, b, c, d;
fi >> x >> y >> a >> b >> c >> d;
vector <int> rez;
for (int i = 1; i <= m; i++)
{
int cost;
if (x == y)
cost = 0;
else
{
int comun = lca(x, y);
cost = min(getminim(x, comun), getminim(y, comun));
}
if (i >= m - pp + 1)
rez.push_back(cost);
int cx = x, cy = y;
x = (cx * a + cy * b) % n + 1;
y = (cy * c + cost * d) % n + 1;
}
reverse(rez.begin(), rez.end());
for (auto x: rez)
fo << x << "\n";
return 0;
}