Pagini recente » Cod sursa (job #2028352) | Cod sursa (job #1683370) | Cod sursa (job #2743100) | Cod sursa (job #834461) | Cod sursa (job #1954077)
#include <iostream>
#include <fstream>
#define nMax 32003
#define logMax 20
using namespace std;
ofstream fout("atac.out");
int n, m, p, A, B, C, D, T[nMax], v[nMax], L[nMax];
typedef struct{
int nod, mn;
} node;
node dp[nMax][logMax];
void set_values()
{
for(int j = 0; (1 << j) <= n; ++j)
for(int i = 1; i <= n; ++i)
dp[i][j] = {-1, -1};
for(int i = 2; i <= n; ++i)
dp[i][0] = {T[i], v[i]};
for(int j = 1; (1 << j) <= n; ++j)
for(int i = 2; i <= n; ++i)
if(dp[i][j - 1].nod != -1){
dp[i][j].nod = dp[dp[i][j - 1].nod][j - 1].nod;
dp[i][j].mn = min(dp[i][j - 1].mn, dp[dp[i][j - 1].nod][j - 1].mn);
}
}
void LCA(int x, int y, int nr)
{
int X = x, Y = y;
int minB = (1 << 30);
if(x == y) minB = 0;
if(L[x] < L[y]) swap(x, y);
int step;
for(step = 0; (1 << step) <= L[x]; ++step);
--step;
for(int i = step; i >= 0; --i)
if(L[x] - (1 << i) >= L[y]){
minB = min(minB, dp[x][i].mn);
x = dp[x][i].nod;
}
for(int i = step; i >= 0; --i)
if(dp[x][i].nod != -1 && dp[x][i].nod != dp[y][i].nod){
minB = min(minB, min(dp[x][i].mn, dp[y][i].mn));
x = dp[x][i].nod;
y = dp[y][i].nod;
}
if(x != y) minB = min(minB, min(v[x], v[y]));
if(nr > m - p)
fout << minB << '\n';
if(nr < m)
LCA(((X * A) % n + (Y * B) % n) % n + 1, ((Y * C) % n + (minB * D) % n) % n + 1, nr + 1);
}
void read()
{
int x, y;
ifstream fin("atac.in");
fin >> n >> m >> p;
for(int i = 2; i <= n; ++i){
fin >> T[i] >> v[i];
L[i] = L[T[i]] + 1;
}
set_values();
fin >> x >> y >> A >> B >> C >> D;
LCA(x, y, 1);
}
int main()
{
read();
return 0;
}