Pagini recente » Cod sursa (job #3225526) | Cod sursa (job #2769929) | Cod sursa (job #2181148) | Cod sursa (job #366616) | Cod sursa (job #2973227)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
int n, m, p, T[20][32005], cost[20][32005], niv[32005], ind, start[32005], sf[32005];
int nod1, nod2, a, b, c, d;
vector<int> G[32005];
void dfs(int nod, int nivel = 1) {
niv[nod] = nivel;
start[nod] = ++ind;
for(auto i : G[nod]) {
dfs(i, nivel + 1);
}
sf[nod] = ++ind;
}
void precalc() {
for(int i = 1; (1 << i) <= n; i++) {
for(int j = 1; j <= n; j++) {
cost[i][j] = min(cost[i - 1][j], cost[i - 1][T[i - 1][j]]);
T[i][j] = T[i - 1][T[i - 1][j]];
}
}
}
bool valid(int x, int y) { // verific daca x este stramos al lui y
return start[x] <= start[y] && sf[y] <= sf[x];
}
int detLca(int x, int y) {
if(valid(x, y)) {
return x;
}
if(valid(y, x)) {
return y;
}
for(int i = 19; i >= 0; i--) {
int z = T[i][x];
if(z != 0 && !valid(z, y)) {
x = z;
}
}
return T[0][x];
}
int det(int x, int y) {
if(x == y) {
return 0;
}
int minim = 0x3f3f3f3f, lca = detLca(x, y);
// determin costul minim de la x la lca sau de la y la lca
for(int nod : {x, y}) {
int diff = niv[nod] - niv[lca];
for(int j = 19; j >= 0; j--) {
if(diff >= (1 << j)) {
diff -= (1 << j);
minim = min(minim, cost[j][nod]);
nod = T[j][nod];
}
}
}
return minim;
}
int main() {
fin >> n >> m >> p;
for(int i = 2; i <= n; i++) {
fin >> T[0][i] >> cost[0][i];
G[T[0][i]].push_back(i);
}
dfs(1);
precalc();
fin >> nod1 >> nod2 >> a >> b >> c >> d;
for(int i = 1; i <= m; i++) {
int ans = det(nod1, nod2);
if(m - i + 1 <= p) {
fout << ans << "\n";
}
nod1 = (nod1 * a + nod2 * b) % n + 1;
nod2 = (nod2 * c + ans * d) % n + 1;
}
return 0;
}