Cod sursa(job #2974951)

Utilizator PatruMihaiPatru Mihai PatruMihai Data 4 februarie 2023 21:41:09
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 33007;
const int LOGMAX = 20;

int n, m, p;
int level[NMAX], pcurent, pstart[NMAX], pend[NMAX], parent[LOGMAX][NMAX], cost[LOGMAX][NMAX];

vector<vector<int>> tree(NMAX);

bool isdad(int x, int y)
{
    return pstart[x] <= pstart[y] && pend[y] <= pend[x];
}

void calculeazatata()
{
    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][parent[i - 1][j]]);
            parent[i][j] = parent[i - 1][parent[i - 1][j]];
        }
    }
}

int _lca(int x, int y)
{
    if (isdad(x, y))
        return x;

    if (isdad(y, x))
        return y;

    for (int p = LOGMAX - 1; p >= 0; --p)
    {
        int z = parent[p][x];
        if (z != 0 && !isdad(z, y))
        {
            x = z;
        }
    }
    return parent[0][x];
}

void dfs(int node, int lvl = 1)
{
    level[node] = lvl;
    pstart[node] = ++pcurent;
    for (int vecin: tree[node])
    {
        dfs(vecin, lvl + 1);
    }
    pend[node] = ++pcurent;
}

int getCost(int x, int y)
{
    if (x == y)
        return 0;

    int lca = _lca(x, y);
    int minimum = INT_MAX;
    for (int node: {x, y})
    {
        int diff = level[node] - level[lca];
        for (int p = LOGMAX - 1; p >= 0; --p)
        {
            if (diff >= (1 << p))
            {
                diff -= (1 << p);
                minimum = min(minimum, cost[p][node]);
                node = parent[p][node];
            }
        }
    }

    return minimum;
}

int main()
{
    fin >> n >> m >> p;
    for (int i = 2; i <= n; ++i)
    {
        fin >> parent[0][i] >> cost[0][i];
        tree[parent[0][i]].push_back(i);
    }

    dfs(1);
    calculeazatata();

    int node1, node2, a, b, c, d;

    fin >> node1 >> node2 >> a >> b >> c >> d;

    for (int i = 1; i <= m; ++i)
    {
        int sol = getCost(node1, node2);
        if (m - i + 1 <= p)
            fout << sol << '\n';

        node1 = (node1 * a + node2 * b) % n + 1;
        node2 = (node2 * c + sol * d) % n + 1;
    }

    return 0;
}