Cod sursa(job #2971346)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 27 ianuarie 2023 01:07:30
Problema Atac Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>

#define infile "atac.in"
#define outfile "atac.out"

using namespace std;

const int MAX_N = 33005;
const int MAX_LOG = 17;
const int INF = 2000000000;

int n;
int level[MAX_N];
int p_current = 0, p_start[MAX_N], p_end[MAX_N];
int parent[MAX_LOG][MAX_N], cost[MAX_LOG][MAX_N];

vector<int> tree[MAX_N];

void dfs(int node, int _level = 1)
{
    level[node] = _level;
    p_start[node] = ++p_current;
    for (int adj : tree[node])
    {
        dfs(adj, _level + 1);
    }
    p_end[node] = ++p_current;
}

bool is_ancestor(int x, int y)
{
    return p_start[x] <= p_start[y] && p_end[y] <= p_end[x];
}

void calcAncestors()
{

    for (int i = 1; (1 << i) <= n; ++i)
    {

        for (int j = 1; j <= n; ++j)
        {

            cost[i][j] = min(cost[i - 1][j], cost[i - 1][parent[i - 1][j]]);
            parent[i][j] = parent[i - 1][parent[i - 1][j]];
        }
    }
}

int getLca(int x, int y)
{
    if (is_ancestor(x, y))
    {
        return x;
    }
    if (is_ancestor(y, x))
    {
        return y;
    }
    for (int p = MAX_LOG - 1; p >= 0; --p)
    {
        int z = parent[p][x];
        if (z != 0 && !is_ancestor(z, y))
        {
            x = z;
        }
    }
    return parent[0][x];
}

int getCost(int x, int y)
{

    if (x == y)
        return INF;

    int lca = getLca(x, y);
    int minimum = INF;
    for (int node : {x, y})
    {
        int diff = level[node] - level[lca];
        for (int p = MAX_LOG - 1; p >= 0; --p)
        {
            if (diff >= (1 << p))
            {
                diff -= (1 << p);
                minimum = min(minimum, cost[p][node]);
                node = parent[p][node];
            }
        }
    }

    return minimum;
}

int main()
{

    ifstream fin(infile);
    ofstream fout(outfile);

    int m, p;
    fin >> n >> m >> p;
    for (int i = 2; i <= n; ++i)
    {
        fin >> parent[0][i] >> cost[0][i];
        tree[parent[0][i]].push_back(i);
    }

    dfs(1);
    calcAncestors();

    int node1, node2, A, B, C, D;

    fin >> node1 >> node2 >> A >> B >> C >> D;

    for (int i = 1; i <= m; ++i)
    {
        int sol = getCost(node1, node2);
        if (m - i + 1 <= p)
            fout << sol << '\n';
        node1 = (node1 * A + node2 * B) % n + 1;
        node2 = (node2 * C + sol * D) % n + 1;
    }

    return 0;
}