Cod sursa(job #2266719)

Utilizator ancabdBadiu Anca ancabd Data 22 octombrie 2018 20:54:16
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

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

#define Inf 0x3f3f3f
#define MAX 32001
#define LOGMAX 20

int nro, m, p, X, Y, A, B, C, D;

vector< vector<int> > G;
vector< vector<int> > rmq, rmqg, v;
vector< pair<int, int> > dad;
vector<int> Se, fap, lvl;
vector<bool> viz;

void Read();
int CalcMin(int x, int y);
int Lca (int x, int y);
void Dfs(int, int);
void Rmq();
void RmqG();
void Init();

int main()
{
    Read();

    Dfs(1, 1);
    Rmq();
    RmqG();

    for (int i = 1, x = X, y = Y; i <= m; i ++)
    {
        int aux = x, auy = y, z;
        int lca = Lca(x, y);

        z = min(CalcMin(x, lca), CalcMin(y, lca));

        if (z == Inf)z = 0;

        x = (aux * A + auy * B) % nro + 1;
        y = (auy * C + z * D) % nro + 1;

        if (i >= m - p + 1)
            fout << z << '\n';
    }
    return 0;
}
void Read()
{
    fin >> nro >> m >> p;

    G = vector< vector<int> >(/*nro + 1*/MAX);
    viz = vector<bool>(/*nro + 1*/MAX, 0);
    fap = vector<int>(/*nro + 1*/MAX);
    dad = vector< pair<int, int> >(/*nro + 1*/MAX);

    for (int i = 2, x, v; i <= nro; i ++)
    {
        fin >> x >> v;
        G[i].push_back(x);
        G[x].push_back(i);
        dad[i] = {x, v};
    }
    fin >> X >> Y >> A >> B >> C >> D;
}
int CalcMin(int x, int y)
{
    if (x == y)return Inf;

    int k = log2(lvl[x] - lvl[y]);
    return min(rmqg[k][x], CalcMin(v[k][x], y));
}
int Lca (int x, int y)
{
    if (x == y)return x;

    x = fap[x];
    y = fap[y];

    if (x > y)swap(x, y);

    int l = log2(y - x + 1);

    if (lvl[rmq[l][x]] < lvl[rmq[l][y - (1 << l)]])
        return Se[rmq[l][x]];
    else return Se[rmq[l][y - (1 << l)]];
}
void Dfs(int node, int l)
{
    viz[node] = 1;

    Se.push_back(node);
    lvl.push_back(l);
    fap[node] = Se.size();

    for (int i = 0; i < G[node].size(); i ++)
    {
        if (!viz[G[node][i]])Dfs(G[node][i], l + 1);

        Se.push_back(node);
        lvl.push_back(l);
    }
}
void Rmq()
{
    int k = Se.size();
    rmq = vector< vector<int> >(/*log2(k) + 2*/LOGMAX, vector<int>(/*nro + 1*/MAX));

    for (int i = 0; i < k; i ++)
        rmq[0][i] = i;

    for (int i = 1; (1 << i) < k; i ++)
        for (int j = 1; j <= k - (1 << i); j ++)
        {
            int l = 1 << (i - 1);
			rmq[i][j] = rmq[i - 1][j];
			if(lvl[rmq[i - 1][j + l]] < lvl[rmq[i][j]])
                rmq[i][j] = rmq[i - 1][j + l];
		}
}
void RmqG()
{
    int k = log2(nro);
    rmqg = vector< vector<int> >(/*k + 2*/LOGMAX, vector<int>(/*nro + 1*/MAX, Inf));
    v = vector< vector<int> >(/*k + 2*/LOGMAX, vector<int>(/*nro + 1*/MAX));

    for (int i = 1; i <= nro; i ++)
    {
        v[0][i] = dad[i].first;
        rmqg[0][i] = dad[i].second;
    }
    for (int i = 1; i <= k; i ++)
        for (int j = 1; j <= nro; j ++)
        {
            v[i][j] = v[i - 1][v[i - 1][j]];
            rmqg[i][j] = min(rmqg[i - 1][j], rmqg[i - 1][v[i - 1][j]]);
        }
}