Cod sursa(job #3304662)

Utilizator AndreiNicolaescuEric Paturan AndreiNicolaescu Data 25 iulie 2025 18:41:20
Problema Atac Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <bits/stdc++.h>
#define int long long
#define cin ci
#define cout co
using namespace std;

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

const int INF = 1e9;
const int Nmax = 32001;
const int Lmax = 16;

int n, m, p;
int anc[Nmax][Lmax], mini[Nmax][Lmax], dist[Nmax];
vector<vector<pair<int, int>>> graf;

void dfs(int node, int par)
{
    dist[node] = dist[par] + 1;
    anc[node][0] = par;
    for (auto &[next, cost] : graf[node])
    {
        if (next != par)
        {
            mini[next][0] = cost;
            dfs(next, node);
        }
    }
}

void binary()
{
    for (int l = 1; l < Lmax; l++)
    {
        for (int node = 1; node <= n; node++)
        {
            int mid = anc[node][l - 1];
            anc[node][l] = anc[mid][l - 1];
            mini[node][l] = min(mini[node][l - 1], mini[mid][l - 1]);
        }
    }
}

pair<int, int> findanc(int node, int steps)
{
    int ans = INF;
    for (int l = 0; l < Lmax; l++)
    {
        if (steps & (1 << l))
        {
            ans = min(ans, mini[node][l]);
            node = anc[node][l];
            if (node == 0) break;
        }
    }
    return {node, ans};
}

int lca(int node1, int node2)
{
    int ans = INF;

    if (dist[node1] < dist[node2])
        swap(node1, node2);

    auto [up_node, min_val] = findanc(node1, dist[node1] - dist[node2]);
    node1 = up_node;
    ans = min(ans, min_val);

    if (node1 == node2)
        return ans;

    for (int l = Lmax - 1; l >= 0; l--)
    {
        if (anc[node1][l] != anc[node2][l])
        {
            ans = min({ans, mini[node1][l], mini[node2][l]});
            node1 = anc[node1][l];
            node2 = anc[node2][l];
        }
    }

    return min({ans, mini[node1][0], mini[node2][0]});
}

int32_t main()
{
    cin >> n >> m >> p;

    graf.assign(n + 1, vector<pair<int, int>>());

    for (int i = 0; i <= n; i++)
    {
        for (int l = 0; l < Lmax; l++)
        {
            mini[i][l] = INF;
            anc[i][l] = 0;
        }
    }

    for (int i = 2; i <= n; i++)
    {
        int x, y;
        cin >> x >> y;
        graf[x].push_back({i, y});
        graf[i].push_back({x, y});
    }

    mini[1][0] = INF;
    dfs(1, 0);
    binary();

    int x, y, A, B, C, D;
    cin >> x >> y >> A >> B >> C >> D;

    for (int i = 1; i <= m; i++)
    {
        int z = lca(x, y);
        if (i > m - p)
            cout << z << '\n';
        x = (x * A + y * B) % n + 1;
        y = (y * C + z * D) % n + 1;
    }

    return 0;
}