Pagini recente » Cod sursa (job #3235189) | Cod sursa (job #1954118)
#include <iostream>
#include <fstream>
#define nMax 32003
#define logMax 20
using namespace std;
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);
}
}
int LCA(int x, int y)
{
int minB = (1 << 30);
if(x == y) return 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]));
return minB;
}
void read_and_solve()
{
int x, y, z;
ifstream fin("atac.in");
ofstream fout("atac.out");
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;
for(int i = 1; i <= m; ++i){
z = LCA(x, y);
if(i > m - p)
fout << z << '\n';
x = ((x * A) % n + (y * B) % n) % n + 1;
y = ((y * C) % n + (z * D) % n) % n + 1;
}
}
int main()
{
read_and_solve();
return 0;
}