Cod sursa(job #3304652)

Utilizator AndreiNicolaescuEric Paturan AndreiNicolaescu Data 25 iulie 2025 18:29:15
Problema Atac Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <bits/stdc++.h>
#define cin ci
#define cout co
#define int long long
using namespace std;
ifstream cin("atac.in");
ofstream cout("atac.out");
const int INF = 1e9;
const int Nmax = 32e3 + 1;
const int Lmax = 21;
int n, m, p, x, y, z, A ,B ,C , D;
int anc[Nmax][Lmax], mini[Nmax][Lmax], dist[Nmax];
vector<vector<pair<int, int>>> graf;
void binary()
{
    for(int l=1; l<Lmax; l++)
        for(int node=1; node<=n; node++)
        {
            anc[node][l] = anc[anc[node][l - 1]][l - 1];
            mini[node][l] = min(mini[node][l - 1], mini[anc[node][l - 1]][l - 1]);
        }
}
pair<int, int> findanc(int node, int nanc)
{
    int ans = INF;
    for(int l=0; l<Lmax; l++)
        if(nanc & (1 << l))
        {
            ans = min(ans, mini[node][l]);
            node = anc[node][l];

        }
    return {node, ans};
}
int lca(int node1, int node2)
{
    int ans = INF;
    if(dist[node1] < dist[node2])
        swap(node1, node2);
    pair<int, int> aux = findanc(node1, dist[node1] - dist[node2]);
    ans = aux.second;
    node1 = aux.first;
    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]});
}
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);
        }
}
int32_t main()
{
    cin >> n >> m >> p;
    graf.assign(n+1, vector<pair<int, int>>());
    for(int i=2; i<=n; i++)
    {
        cin >> x >> y;
        graf[x].push_back({i, y});
        graf[i].push_back({x, y});
    }
    dfs(1, 0);
    mini[1][0] = INF;
    binary();
    cin >> x >> y >> A >> B >> C >> D;
    for(int i=1; i<=m; i++)
    {
        int z = lca(x, y);
        if(m - p < i)
            cout << z << '\n';
        x = (x * A + y * B) % n + 1;
        y = (y * C + z * D) % n + 1;
    }
    return 0;
}