Cod sursa(job #3272192)

Utilizator CaldareaCiprianCaldarea Ciprian CaldareaCiprian Data 28 ianuarie 2025 19:38:25
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

using ll = long long;
using VI = vector<ll>;
using VVI = vector<VI>;
using VPI = vector<pair<ll, ll>>;
using VVPI = vector<VPI>;

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

VVPI G;
VVPI up;
VI v, niv;
ll n, K, q, logaritm;
const ll INF = (1 << 29);

void DFS(ll x, ll p)
{
    if (x == 1)
        v[x] = INF;

    up[0][x].first = p;
    up[0][x].second = v[x];

    niv[x] = niv[p] + 1;

    for (auto& y : G[x])
    {
        if (y.first == p)
            continue;

        v[y.first] = y.second;
        DFS(y.first, x);
    }

}

ll LCA(ll x, ll y)
{
    if (x == y)
        return 0;

    if (niv[x] > niv[y])
        swap(x, y);


    ll mi = INF;

    for (ll i = logaritm; i >= 0; --i)
    {
        if (niv[up[i][y].first] >= niv[x])
        {
            mi = min(mi, up[i][y].second);
            y = up[i][y].first;

        }
    }

    for (ll i = logaritm; i >= 0; --i)
    {
        if (up[i][y].first != up[i][x].first)
        {
            mi = min(mi, up[i][y].second);
            mi = min(mi, up[i][x].second);
            y = up[i][y].first;
            x = up[i][x].first;
        }
    }


    mi = min(mi, up[0][y].second);
    mi = min(mi, up[0][x].second);
    return mi;


}

int main()
{
    fin >> n >> K >> q;
    ll x, cost;
    G = VVPI(n + 1);
    logaritm = ceil(log2(n));
    up = VVPI(logaritm + 2, VPI(n + 1, make_pair(INF, INF)));
    v = niv = VI(n + 1, -1);

    for (ll i = 1;  i < n; ++i)
    {
        fin >> x >> cost;
        G[i + 1].emplace_back(x, cost);
        G[x].emplace_back(i + 1, cost);
    }

    DFS(1, 1);

    for (ll k = 1; k <= logaritm; ++k)
    {
        for (ll i = 1; i <= n; ++i)
        {
            up[k][i].first = up[k - 1][up[k - 1][i].first].first;
            up[k][i].second = min(up[k - 1][i].second, up[k - 1][up[k - 1][i].first].second);
        }
    }

    ll X, Y, A, B, C, D, Z = 0;
    fin >> X >> Y >> A >> B >> C >> D;
    VI last;
    for (ll i = 1; i <= K; ++i)
    {
        if (i > 1)
        {
            X = (X * A + Y * B) % n + 1;
            Y = (Y * C + Z * D) % n + 1;
        }

        Z = LCA(X, Y);
        if (K - i + 1 <= q)
            last.emplace_back(Z);
    }

    reverse(last.begin(), last.end());

    for (auto x : last)
        fout << x << '\n';
}