Cod sursa(job #3278128)

Utilizator ALEXANDRUspargoaseAlexandru Joita ALEXANDRUspargoase Data 18 februarie 2025 18:07:08
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.42 kb
#include <fstream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

ifstream cin("atac.in");
ofstream cout("atac.out");

const int Nmax = 32001;
vector<pair<int, int>> tree[Nmax];
vector<int> rang(Nmax), par(Nmax), cost(Nmax);

struct SparseTable
{
    int n;
    vector<vector<int>> spt; // parent jumps
    vector<vector<int>> mn;  // min edge cost along the jump

    int getLog(int x)
    {
        return 31 - __builtin_clz(x);
    }

    SparseTable(int n, vector<int> &par, vector<int> &cost) : n(n)
    {
        int logN = getLog(n);
        spt.resize(logN + 1, vector<int>(n + 1, 0));
        mn.resize(logN + 1, vector<int>(n + 1, INT_MAX));

        for (int i = 1; i <= n; i++)
        {
            spt[0][i] = par[i];
            mn[0][i] = cost[i];
        }

        for (int i = 1; i <= logN; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                spt[i][j] = spt[i - 1][spt[i - 1][j]];
                mn[i][j] = min(mn[i - 1][j], mn[i - 1][spt[i - 1][j]]);
            }
        }
    }

    // Lifts node 'a' up by 'diff' levels,
    // returning the new node and the minimum edge cost along that lifting.
    pair<int, int> lift(int a, int diff)
    {
        if (diff == 0)
            return {a, INT_MAX};
        int min_val = INT_MAX;
        int logD = getLog(diff);
        for (int i = logD; i >= 0; i--)
        {
            if (diff >= (1 << i))
            {
                min_val = min(min_val, mn[i][a]);
                a = spt[i][a];
                diff -= (1 << i);
            }
        }
        return {a, min_val};
    }

    // Returns a pair: the LCA of a and b, and the minimum edge cost along the path from a->LCA and b->LCA.
    pair<int, int> query(int a, int b)
    {
        int min_val = INT_MAX;
        if (rang[a] < rang[b])
            swap(a, b);

        int diff = rang[a] - rang[b];
        auto res = lift(a, diff);
        a = res.first;
        min_val = min(min_val, res.second);

        if (a == b)
            return {a, min_val};

        int logD = getLog(rang[a]);
        for (int i = logD; i >= 0; i--)
        {
            if (spt[i][a] != 0 && spt[i][a] != spt[i][b])
            {
                min_val = min({min_val, mn[i][a], mn[i][b]});
                a = spt[i][a];
                b = spt[i][b];
            }
        }

        min_val = min({min_val, mn[0][a], mn[0][b]});
        return {spt[0][a], min_val};
    }
};

void dfs(int nod, int lev, int parent)
{
    rang[nod] = lev;

    for (auto it : tree[nod])
        if (it.first != parent)
        {
            par[it.first] = nod;
            cost[it.first] = it.second;
            dfs(it.first, lev + 1, nod);
        }
}

int main()
{
    int n, m, p;
    cin >> n >> m >> p;
    for (int i = 2; i <= n; i++)
    {
        int y, c;
        cin >> y >> c;
        tree[i].push_back({y, c});
        tree[y].push_back({i, c});
    }

    dfs(1, 1, 0);
    SparseTable st(n, par, cost);

    int x, y, a, b, c, d;
    cin >> x >> y >> a >> b >> c >> d;
    for (int i = 1; i <= m; i++)
    {
        auto res = st.query(x, y);
        int z = res.second;
        if (z == INT_MAX)
            z = 0;

        if (m - i + 1 <= p)
            cout << z << '\n';

        x = (x * a + y * b) % n + 1, y = (y * c + z * d) % n + 1;
    }

    return 0;
}