Cod sursa(job #2989001)

Utilizator Matei_MunteanuMunteanu Matei Ioan Matei_Munteanu Data 5 martie 2023 18:08:42
Problema Atac Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.08 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 32004;
const int K = 15;
const int INF = 100000004;

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

int n, m, p;
vector<pair<int, int>> adj[NMAX];
int x, y, a, b, c, d;
int z;

struct LowestCommonAncestor
{
    int t_in[NMAX];
    int t_out[NMAX];
    pair<int, int> up[NMAX][K + 2];
    int dfstimer;

    void _dfs(int v, int p, int cost)
    {
        t_in[v] = ++dfstimer;
        up[v][0].first = p;
        up[v][0].second = cost;
        for (int i = 1; i <= K; i++)
        {
            up[v][i].first = up[up[v][i - 1].first][i - 1].first;
            up[v][i].second = min(up[v][i - 1].second, up[up[v][i - 1].first][i - 1].second);
        }
        for (auto edge : adj[v])
        {
            int u = edge.first;
            int c = edge.second;
            if (u != p)
            {
                _dfs(u, v, c);
            }
        }
        t_out[v] = ++dfstimer;
    }

    void init()
    {
        dfstimer = 0;
        _dfs(1, 1, INF);
    }

    bool is_ancestor(int u, int v)
    {
        return (t_in[u] <= t_in[v] && t_out[u] >= t_out[v]);
    }

    int min_edge(int u, int v)
    {
        int rez = INF;
        if (is_ancestor(u, v))
        {
            for (int i = K; i >= 0; i--)
            {
                if (is_ancestor(u, up[v][i].first))
                {
                    rez = min(rez, up[v][i].second);
                    v = up[v][i].first;
                }
            }
            return rez;
        }
        if (is_ancestor(v, u))
        {
            for (int i = K; i >= 0; i--)
            {
                if (is_ancestor(v, up[u][i].first))
                {
                    rez = min(rez, up[u][i].second);
                    u = up[u][i].first;
                }
            }
            return rez;
        }
        int copyu = u;
        for (int i = K; i >= 0; i--)
        {
            if (!is_ancestor(up[u][i].first, v))
            {
                rez = min(rez, up[u][i].second);
                u = up[u][i].first;
            }
        }
        rez = min(rez, up[u][0].second);
        u = copyu;
        for (int i = K; i >= 0; i--)
        {
            if (!is_ancestor(up[v][i].first, u))
            {
                rez = min(rez, up[v][i].second);
                v = up[v][i].first;
            }
        }
        rez = min(rez, up[v][0].second);
        return rez;
    }
} LCA;

int main()
{
    fin >> n >> m >> p;
    for (int i = 2; i <= n; i++)
    {
        int b, c;
        fin >> b >> c;
        adj[i].push_back({b, c});
        adj[b].push_back({i, c});
    }
    fin >> x >> y >> a >> b >> c >> d;
    if (x == y)
    {
        fout << 0;
        return 0;
    }
    LCA.init();
    for (int i = 1; i <= m; i++)
    {
        z = LCA.min_edge(x, y);
        if (i >= (m - p + 1))
        {
            fout << z << '\n';
        }
        x = ((x * a + y * b) % n) + 1;
        y = ((y * c + z * d) % n) + 1;
    }
    return 0;
}