Cod sursa(job #2346706)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 17 februarie 2019 23:20:52
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

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

const int NMax = 32000, oo = 1e9;

int N, M, P, X, Y, A, B, C, D, Z, Lev[NMax + 5], T[20][NMax + 5], DT[20][NMax + 5];

struct str{int n, c;};

vector <str> G[NMax + 5];

void Read()
{
    fin >> N >> M >> P;

    for(int i = 2, x, c; i <= N; i++)
    {
        fin >> x >> c;

        G[i].push_back({x, c});
        G[x].push_back({i, c});
    }
    fin >> X >> Y >> A >> B >> C >> D;

    fin.close();
}

void Precalc()
{
    for(int i = 1; (1 << i) <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            T[i][j] = T[i - 1][T[i - 1][j]];

            if(T[i][j])
                DT[i][j] = min(DT[i - 1][j], DT[i - 1][T[i - 1][j]]);
        }
    }
}

void DFS(int Nod, int Tata)
{
    Lev[Nod] = Lev[Tata] + 1, T[0][Nod] = Tata;

    for(auto Vecin : G[Nod])
    {
        if(Vecin.n == Tata) continue;

        DT[0][Vecin.n] = Vecin.c;
        DFS(Vecin.n, Nod);
    }
}

int Stramos(int Nod, int P)
{
    int k = 0;

    while(P) {
        if(P & 1) Nod = T[k][Nod];

        P >>= 1, k++;
    }
    return Nod;
}

int LCA(int x, int y)
{
    if(Lev[x] < Lev[y]) swap(x, y);

    if(Lev[x] != Lev[y])
        x = Stramos(x, Lev[x] - Lev[y]);

    if(x == y) return x;

    for(int i = log2(Lev[x]); i >= 0; i--)
    {
        if(T[i][x] != T[i][y])
            x = T[i][x], y = T[i][y];
    }
    return T[0][x];
}

int Bomb(int Nod, int F)
{
    int k = 0, Sol = oo, P = Lev[Nod] - Lev[F];

    while(P)
    {
        if(P & 1) Sol = min(Sol, DT[k][Nod]), Nod = T[k][Nod];

        P >>= 1, k++;
    }
    return Sol;
}

void SolveP()
{
    for(int i = 1; i <= M; i++)
    {
        int Nod = LCA(X, Y);

        Z = min(Bomb(X, Nod), Bomb(Y, Nod));

        if(X == Y) Z = 0;

        if(M - i + 1 <= P)
            fout << Z << '\n';

        X = (X * A + Y * B) % N + 1;
        Y = (Y * C + Z * D) % N + 1;
    }
    fout.close();
}

int main()
{
    Read();
    DFS(1, 0);
    Precalc();
    SolveP();

    return 0;
}