Cod sursa(job #2655828)

Utilizator sebimihMihalache Sebastian sebimih Data 5 octombrie 2020 18:06:12
Problema Atac Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("atac.in");
ofstream fout("atac.out");

const int N = 32005;
const int LOG = 15;
const int inf = 1 << 30;

int n, p, m;
int t[N], rmq[LOG][N], anc[LOG][N], lvl[N];
vector<int> g[N];

void df(int x, int l)
{
    lvl[x] = l;
    for (int y : g[x])
        df(y, l + 1);
}

void prep()
{
    df(1, 0);

    for (int i = 1; i <= n; i++)
        anc[0][i] = t[i];

    for (int p = 1; (1 << p) <= n; p++)
        for (int i = 1; i <= n; i++)
        {
            anc[p][i] = anc[p - 1][anc[p - 1][i]];
            rmq[p][i] = min(rmq[p - 1][i], rmq[p - 1][anc[p - 1][i]]);
        }
}

int solveQuery(int x, int y)
{
    if (x == y)
        return 0;

    if (lvl[x] < lvl[y])
        swap(x, y);

    int ans = inf;
    int dif = lvl[x] - lvl[y];
    for (int i = 0; (1 << i) <= n; i++)
        if (dif & (1 << i))
        {
            ans = min(ans, rmq[i][x]);
            x = anc[i][x];
        }

    for (int i = LOG - 1; i >= 0; i--)
        if (anc[i][x] != anc[i][y])
        {
            ans = min(ans, rmq[i][x]);
            ans = min(ans, rmq[i][y]);
            x = anc[i][x];
            y = anc[i][y];
        }

    ans = min(ans, rmq[0][x]);
    ans = min(ans, rmq[0][y]);
    return ans;
}

int main()
{
    fin >> n >> m >> p;
    for (int i = 2; i <= n; i++)
    {
        int y, c;
        fin >> y >> c;
        g[y].push_back(i);
        t[i] = y;
        rmq[0][i] = c;
    }

    prep();

    int x, y, z, a, b, c, d;
    fin >> x >> y >> a >> b >> c >> d;
    for (int i = 0; i < m; i++)
    {
        z = solveQuery(x, y);

        if (i >= m - p)
            fout << z << '\n';

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

    return 0;
}