Cod sursa(job #3338688)

Utilizator parus_majorParus Major parus_major Data 4 februarie 2026 14:22:13
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <climits>

using namespace std;

ifstream fin("atac.in");
ofstream fout("atac.out");

const int MAXL = 16;
const int MAXN = 32002;

int N, M, P;
int v, x, y, a, b, c, d, ans;
int dp[MAXL][MAXN], f[MAXL][MAXN];
int lv[MAXN];
vector<int> childp[MAXN];

void df(int node, int depth) {
    lv[node] = depth;
    for (const int& c : childp[node])
        df(c, depth + 1);
}

int compute(int x, int y) {
    int ans = INT_MAX;
    if (lv[x] < lv[y]) swap(x, y);
    const int delta = lv[x] - lv[y];
    for (int i = 0; i < MAXL; ++i) {
        if (delta & (1 << i)) {
            ans = min(ans, dp[i][x]);
            x = f[i][x];
        }
    }
    for (int i = MAXL - 1; i >= 0; --i) {
        if (f[i][x] != f[i][y]) {
            ans = min(ans, dp[i][x]);
            x = f[i][x];
            ans = min(ans, dp[i][y]);
            y = f[i][y];
        }
    }
    if (x != y) {
        ans = min(ans, dp[0][x]);
        ans = min(ans, dp[0][y]);
    }
    if (ans == INT_MAX) ans = 0;
    return ans;
}

int main()
{
    fin >> N >> M >> P;
    for (int i = 2; i <= N; ++i) {
        fin >> y >> v;
        f[0][i] = y;
        dp[0][i] = v;
        childp[y].push_back(i);
    }
    for (int i = 1; i < MAXL; ++i) {
        for (int j = 1; j <= N; ++j) {
            f[i][j] = f[i - 1][f[i - 1][j]];
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][f[i - 1][j]]);
        }
    }
    df(1, 1);

    fin >> x >> y >> a >> b >> c >> d;
    for (int i = 1; i <= M; ++i) {
        ans = compute(x, y);
        if (i >= M - P + 1) {
            fout << ans << '\n';
        }
        x = (x * a + y * b) % N + 1;
        y = (y * c + ans * d) % N + 1;
    }

    return 0;
}