Cod sursa(job #2655827)

Utilizator Marius7122FMI Ciltea Marian Marius7122 Data 5 octombrie 2020 17:59:33
Problema Atac Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 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 = LOG-1; i >= 0; 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;
}