Pagini recente » Arhiva de probleme | Cod sursa (job #290417) | Istoria paginii utilizator/mary99 | Cod sursa (job #1520990) | Cod sursa (job #2488864)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int nmax = 32000, lgmax = 15, inf = 0x3f3f3f3f;
struct Street{
int nod, cost;
Street(int n, int c) : nod(n), cost(c) {}
};
vector <Street> g[nmax + 5];
int n, m, p, A, B, C, D, X, Y, level[nmax + 5], a[lgmax][nmax + 5], c[lgmax][nmax + 5], log2[nmax + 5];
void Read(){
fin >> n >> m >> p;
for (int i = 2; i <= n; i++){
int x, c;
fin >> x >> c;
g[i].push_back({x, c});
g[x].push_back({i, c});
}
fin >> X >> Y >> A >> B >> C >> D;
}
void DFS(int nod, int tata){
level[nod] = level[tata] + 1;
a[0][nod] = tata;
for (auto i : g[nod])
if (i.nod != tata){
DFS(i.nod, nod);
c[0][i.nod] = i.cost;
}
}
void Precalc(){
DFS(1, 0);
for (int i = 2; i <= n; i++)
log2[i] = log2[i / 2] + 1;
for (int i = 1; i <= log2[n]; i++)
for (int j = 1; j <= n; j++){
a[i][j] = a[i - 1][a[i - 1][j]];
c[i][j] = min(c[i - 1][j], c[i - 1][c[i - 1][j]]);
}
}
int LCA(int x, int y){
if (level[x] > level[y])
swap(x, y);
while (level[x] < level[y]){
int dif = level[y] - level[x];
y = a[log2[dif]][y];
}
if (x == y)
return x;
for (int i = log2[level[x]]; i >= 0; i--)
if (a[i][x] != a[i][y]){
x = a[i][x];
y = a[i][y];
}
return a[0][x];
}
int Min(int nod, int lca){
int sol = inf;
while (level[lca] < level[nod]){
int dif = level[nod] - level[lca];
sol = min(sol, c[log2[dif]][nod]);
nod = a[log2[dif]][nod];
}
return sol;
}
int main(){
Read();
Precalc();
for (int i = 1; i <= m; i++){
int lca = LCA(X, Y);
int Z = min(Min(X, lca), Min(Y, lca));
if (X == Y)
Z = 0;
if (i > m - p)
fout << Z << '\n';
int X1, Y1;
X1 = (X * A + Y * B) % n + 1;
Y1 = (Y * C + Z * D) % n + 1;
X = X1;
Y = Y1;
}
return 0;
}