Cod sursa(job #2640479)

Utilizator BAlexandruBorgovan Alexandru BAlexandru Data 6 august 2020 16:15:55
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int INF = 2000000000;

struct edge
{
    int dest, weight;
};

int n, m, p;
int x, y, z, a, b, c, d;

int depth[32001];

int log2[32001];

pair < int, int > dp[32001][15];

vector < edge > graph[32001];

void dfs(int node, int d, edge parent)
{
    depth[node] = d;

    dp[node][0].first = parent.dest;
    dp[node][0].second = parent.weight;

    for (auto it : graph[node])
        if (it.dest != parent.dest)
            dfs(it.dest, d + 1, {node, it.weight});
}

pair < int, int > LCA(int node1, int node2)
{
    if (node1 == node2)
        return {node1, 0};

    if (depth[node1] < depth[node2])
        swap(node1, node2);

    int minWeight = INF;

    for (int i=log2[depth[node1]]; i>=0; i--)
        if (depth[node1] - (1<<i) >= depth[node2])
        {
            minWeight = min(minWeight, dp[node1][i].second);
            node1 = dp[node1][i].first;
        }

    if (node1 == node2)
        return {node1, minWeight};

    for (int i=log2[depth[node1]]; i>=0; i--)
        if (dp[node1][i].first && dp[node1][i].first != dp[node2][i].first)
        {
            minWeight = min(minWeight, min(dp[node1][i].second, dp[node2][i].second));
            node1 = dp[node1][i].first;
            node2 = dp[node2][i].first;
        }

    int lca = dp[node1][0].first;
    minWeight = min(minWeight, min(dp[node1][0].second, dp[node2][0].second));

    return {lca, minWeight};
}

int main()
{
    f >> n >> m >> p;

    for (int i=2; i<=n; i++)
    {
        int u, v; f >> u >> v;
        graph[i].push_back({u, v});
        graph[u].push_back({i, v});
    }

    f >> x >> y >> a >> b >> c >> d;

    dfs(1, 0, {0, 0});

    for (int i=1; (1<<i)<=n; i++)
        for (int j=1; j<=n; j++)
        {
            dp[j][i].first = dp[dp[j][i-1].first][i-1].first;
            dp[j][i].second = min(dp[j][i-1].second, dp[dp[j][i-1].first][i-1].second);
        }

    for (int i=2; i<=n; i++)
        log2[i] = log2[i/2] + 1;


    for (int i=1; i<=m; i++)
    {
        z = LCA(x, y).second;

        if (i > m - p)
            g << z << "\n";

        x = (x * a + y * b) % n + 1;
        y = (y * c + z * d) % n + 1;
    }

    return 0;
}