Cod sursa(job #2989010)

Utilizator Matei_MunteanuMunteanu Matei Ioan Matei_Munteanu Data 5 martie 2023 18:17:51
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.3 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 <= n; i++)
    // {
    //     for (int j = 1; j <= n; j++)
    //     {
    //         cout << i << ' ' << j << ' ' << LCA.min_edge(i, j) << '\n';
    //     }
    // }
    for (int i = 1; i <= m; i++)
    {
        z = (x == y ? 0 : 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;
}