Cod sursa(job #2499772)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 26 noiembrie 2019 18:59:01
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.78 kb
#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

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

const int NMAX = 32000;
const int LOGMAX = 16;

int N, M, P, res;
int X, Y, A, B, C, D;

vector < pair <int, int> > g[NMAX + 5];

int h[NMAX + 5], firstAp[NMAX + 5];
int ancestor[LOGMAX + 2][NMAX + 5], costMinUp[LOGMAX + 2][NMAX + 5];

vector < int > rmq[LOGMAX + 5];

void dfs(int node, int dad)
{
    h[node] = h[dad] + 1;

    for(int i = 1; i <= LOGMAX; i++)
        if((1 << i) > h[node])
            break;
        else
        {
            ancestor[i][node] = ancestor[i - 1][ancestor[i - 1][node]];
            costMinUp[i][node] = min(costMinUp[i - 1][node], costMinUp[i - 1][ancestor[i - 1][node]]);
        }

    firstAp[node] = rmq[0].size();
    rmq[0].push_back(node);

    for(auto it : g[node])
        if(it.first != dad)
        {
            ancestor[0][it.first] = node;
            costMinUp[0][it.first] = it.second;

            dfs(it.first, node);

            rmq[0].push_back(node);
        }
}

int Merge(int A, int B)
{
    if(h[A] < h[B])
        return A;

    return B;
}

void buildRmq()
{
    for(int i = 1; i <= LOGMAX; i++)
        if((1 << i) > (int)rmq[0].size())
            break;
        else
        {
            for(int j = 0; j < (int)rmq[0].size(); j++)
                if(j + (1 << i) > (int)rmq[0].size())
                    break;
                else
                    rmq[i].push_back(Merge(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]));
        }
}

int Query(int A, int B)
{
    int AA = A, BB = B;

    A = firstAp[A];
    B = firstAp[B];

    if(A > B) swap(A, B);

    int l = log2(B - A + 1);
    int lca = Merge(rmq[l][A], rmq[l][B - (1 << l) + 1]);

    int minEdgeFromA = 1e6, minEdgeFromB = 1e6;

    int hA = h[AA], hB = h[BB], hlca = h[lca];

    for(int i = LOGMAX; i >= 0; i--)
    {
        if(hA - (1 << i) >= hlca)
        {
            minEdgeFromA = min(minEdgeFromA, costMinUp[i][AA]);
            AA = ancestor[i][AA];
            hA = h[AA];
        }

        if(hB - (1 << i) >= hlca)
        {
            minEdgeFromB = min(minEdgeFromB, costMinUp[i][BB]);
            BB = ancestor[i][BB];
            hB = h[BB];
        }
    }

    return min(minEdgeFromA, minEdgeFromB);
}

int main()
{
    fin >> N >> M >> P;

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

        g[i].push_back({x, y});
        g[x].push_back({i, y});
    }

    fin >> X >> Y >> A >> B >> C >> D;

    dfs(1, 0);
    buildRmq();

    for(int i = 1; i <= M; i++)
    {
        if(X == Y)
            res = 0;
        else
            res = Query(X, Y);

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

        X = (1LL * X * A + Y * B) % N + 1;
        Y = (1LL * Y * C + res * D) % N + 1;
    }

    return 0;
}