Pagini recente » Cod sursa (job #2116726) | Cod sursa (job #935331) | Sandbox | Profil TheSlorrow44 | Cod sursa (job #2488891)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int nmax = 32000, lgmax = 17, inf = 0x3f3f3f3f;
struct Street{
int nod, cost;
};
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, y;
fin >> x >> y;
g[i].push_back({x, y});
g[x].push_back({i, y});
}
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 Min(int x, int y){
if (x == y)
return 0;
int sol = inf;
if (level[x] > level[y])
swap(x, y);
while (level[x] < level[y]){
int dif = level[y] - level[x];
sol = min(sol, c[log2[dif]][y]);
y = a[log2[dif]][y];
}
if (x == y)
return sol;
for (int i = log2[level[x]]; i >= 0; i--)
if (a[i][x] != a[i][y]){
sol = min(sol, c[i][x]);
x = a[i][x];
sol = min(sol, c[i][y]);
y = a[i][y];
}
sol = min(sol, c[0][x]);
sol = min(sol, c[0][y]);
return sol;
}
int main(){
Read();
Precalc();
for (int i = 1; i <= m; i++){
int Z = Min(X, Y);
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;
}