Cod sursa(job #3299583)

Utilizator Cristian_NegoitaCristian Negoita Cristian_Negoita Data 8 iunie 2025 17:01:42
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int NMAX = 32001, LOG = 16, INF = INT_MAX;
int n, m, p, up[NMAX][LOG], depth[NMAX], min_edge[NMAX][LOG];
vector<pair<int, int>> adj[NMAX];

void dfs(int node, int parent, int cost)
{
    up[node][0] = parent;
    min_edge[node][0] = cost;
    depth[node] = depth[parent] + 1;
    for(pair<int, int> child : adj[node])
        if(child.first != parent)
            dfs(child.first, node, child.second);
}

void precalculare()
{
    for(int k = 1; k < LOG; k++)
    {
        for(int node = 1; node <= n; node++)
        {
            up[node][k] = up[up[node][k - 1]][k - 1];
            min_edge[node][k] = min(min_edge[node][k - 1], min_edge[up[node][k - 1]][k - 1]);
        }
    }
}

int lca(int u, int v)
{
    if(u == v)
        return 0;
    if(depth[u] < depth[v])
        swap(u, v);
    int ans = INF;
    for(int k = LOG - 1; k >= 0; k--)
    {
        if(depth[up[u][k]] >= depth[v])
        {
            ans = min(ans, min_edge[u][k]);
            u = up[u][k];
        }
    }
    if(u == v)
        return ans;

    for(int k = LOG - 1; k >= 0; k--)
    {
        if(up[u][k] != up[v][k])
        {
            ans = min({ans, min_edge[u][k], min_edge[v][k]});
            u = up[u][k];
            v = up[v][k];
        }
    }
    return min({ans, min_edge[u][0], min_edge[v][0]});
}

int main()
{
    fin >> n >> m >> p;
    for(int i = 2; i <= n; i++)
    {
        int u, v;
        fin >> u >> v;
        adj[u].emplace_back(i, v);
        adj[i].emplace_back(u, v);
    }
    dfs(1, 0, INF);
    precalculare();

    int x, y, A, B, C, D;
    fin >> x >> y >> A >> B >> C >> D;
    for(int i = 1; i <= m; i++)
    {
        int z = lca(x, y);
        if(i > m - p)
            fout << z << "\n";
        x = (x * A + y * B) % n + 1;
        y = (y * C + z * D) % n + 1;
    }

    fin.close();
    fout.close();
    return 0;
}