Cod sursa(job #2776036)

Utilizator Edyci123Bicu Codrut Eduard Edyci123 Data 18 septembrie 2021 15:05:25
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <bits/stdc++.h>
#define LOG 19
#define DIM 32005

using namespace std;

ifstream f("atac.in");
ofstream g("atac.out");

int n, m, k, up[LOG + 1][DIM], mini[LOG + 1][DIM], depth[DIM];
int x, y, a, b, c, d;
bitset <DIM> v;
vector <pair <int, int>> edges[DIM];
deque <int> Q;

void dfs(int nod, int niv)
{
    depth[nod] = niv;
    v[nod] = 1;
    for(auto child : edges[nod])
        if(!v[child.first])
        {
            up[0][child.first] = nod;
            mini[0][child.first] = child.second;
            for(int i = 1; i <= LOG; i++)
            {
                up[i][child.first] = up[i - 1][up[i - 1][child.first]];
                mini[i][child.first] = min(mini[i - 1][child.first], mini[i - 1][up[i - 1][child.first]]);
            }
            dfs(child.first, niv + 1);
        }
}

int lca(int a, int b)
{
    if(a == b)
        return 0;
    int ans = INT_MAX;
    if(depth[a] < depth[b])
        a = b;
    int k = depth[a] - depth[b];
    for(int i = LOG; i >= 0; i--)
        if(k & (1 << i))
            ans = min(ans, mini[i][a]), a = up[i][a];
    for(int i = LOG; i >= 0; i--)
        if(up[i][a] != up[i][b])
        {
            ans = min(ans, mini[i][a]);
            ans = min(ans, mini[i][b]);
            a = up[i][a];
            b = up[i][b];
        }
    ans = min(ans, mini[0][a]);
    ans = min(ans, mini[0][b]);
    return ans;
}

int main()
{
    f >> n >> m >> k;
    const int MOD = n;

    for(int i = 2; i <= n; i++)
    {
        int x, y;
        f >> x >> y;
        edges[i].push_back(make_pair(x, y));
        edges[x].push_back(make_pair(i, y));
    }
    dfs(1, 0);

    f >> x >> y >> a >> b >> c >> d;
    for(int i = 1; i <= m; i++)
    {
        int p = lca(x, y);
        Q.push_back(p);
        x = (x * a + y * b) % MOD + 1;
        y = (y * c + p * d) % MOD + 1;
    }
    for(int i = m - k; i < m; i++)
        g << Q[i] << "\n";

    return 0;
}