Cod sursa(job #2789379)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 27 octombrie 2021 14:51:32
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.94 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <climits>

using namespace std;

const int NMAX = 32000;

const int LOGMAX = 14;

int n;

vector<pair<int, int>> graf[1 + NMAX];
bool vizitat[1 + NMAX];
pair<int, int> minimeLog[1 + LOGMAX][1 + NMAX];
int h[1 + NMAX];
vector<int> liniarizare;
int primaAparitie[1 + NMAX];
int putere2Max[1 + 2 * NMAX - 1];
pair<int, int> rmq[1 + 2 * NMAX - 1][1 + LOGMAX];

vector<int> sol;

void dfs(int nod, int t, int c, int adanc)
{
    vizitat[nod] = true;
    minimeLog[0][nod].first = t;
    minimeLog[0][nod].second = c;
    h[nod] = adanc;

    liniarizare.push_back(nod);
    primaAparitie[nod] = liniarizare.size() - 1;

    for (int i = 0; i < graf[nod].size(); i++)
    {
        if (!vizitat[graf[nod][i].first]) /// nu trebuie sa comparam cu tatal, pentru ca e deja vizitat
        {
            dfs(graf[nod][i].first, nod, graf[nod][i].second, adanc + 1);

            liniarizare.push_back(nod);
        }
    }
}

void precalcPutere2()
{
    int putere2 = 1;
    int exp = 0;

    for (int i = 1; i <= 2 * n - 1; i++)
    {
        if (putere2 * 2 <= i)
        {
            putere2 *= 2;
            exp++;
        }

        putere2Max[i] = exp;
    }
}

void precalcMinLog()
{
    minimeLog[0][0].first = 0;
    minimeLog[0][0].second = INT_MAX;

    for (int i = 1; i <= putere2Max[n]; i++)
    {
        minimeLog[i][0].first = 0;
        minimeLog[i][0].second = INT_MAX;

        for (int j = 1; j <= n; j++)
        {
            minimeLog[i][j].first = minimeLog[i - 1][minimeLog[i - 1][j].first].first;
            minimeLog[i][j].second = min(minimeLog[i - 1][j].second, minimeLog[i - 1][minimeLog[i - 1][j].first].second);
        }
    }
}

void calcRMQ()
{
    for (int i = 1; i <= 2 * n - 1; i++)
    {
        rmq[i][0].first = liniarizare[i];
        rmq[i][0].second = h[liniarizare[i]];
    }

    for (int l = 1; (1 << l) <= 2 * n - 1; l++)
    {
        for (int i = 1; i <= 2 * n - 1 - (1 << l) + 1; i++)
        {
            if (rmq[i][l - 1].second < rmq[i + (1 << (l - 1))][l - 1].second)
            {
                rmq[i][l].first = rmq[i][l - 1].first;
                rmq[i][l].second = rmq[i][l - 1].second;
            }
            else
            {
                rmq[i][l].first = rmq[i + (1 << (l - 1))][l - 1].first;
                rmq[i][l].second = rmq[i + (1 << (l - 1))][l - 1].second;
            }
        }
    }
}

int minimLant(int nodCrt, int stramos)
{
    int distanta = h[nodCrt] - h[stramos];

    int minim = INT_MAX;

    int indexLog = 0;

    while (distanta > 0)
    {
        if ((1 << indexLog) & distanta)
        {
            distanta -= (1 << indexLog);

            minim = min(minim, minimeLog[indexLog][nodCrt].second);
            nodCrt = minimeLog[indexLog][nodCrt].first;
        }

        indexLog++;
    }

    return minim;
}

int main()
{
    ifstream in("atac.in");
    ofstream out("atac.out");

    int m, p;
    in >> n >> m >> p;

    for (int x = 2; x <= n; x++)
    {
        int y, c;
        in >> y >> c;

        graf[x].emplace_back(make_pair(y, c));
        graf[y].emplace_back(make_pair(x, c));
    }

    liniarizare.push_back(0);
    dfs(1, 0, INT_MAX, 1);
    precalcPutere2();
    precalcMinLog();
    calcRMQ();

    int x, y;
    in >> x >> y;
    int a, b, c, d;
    in >> a >> b >> c >> d;

    int xCrt = x;
    int yCrt = y;

    for (int i = 1; i <= m; i++)
    {
        int xFolosit = xCrt;
        int yFolosit = yCrt;

        if (xFolosit != yFolosit)
        {
            if (primaAparitie[xFolosit] > primaAparitie[yFolosit])
                swap(xFolosit, yFolosit);

            int stramosComun;

            if (rmq[primaAparitie[xFolosit]][putere2Max[primaAparitie[yFolosit] - primaAparitie[xFolosit] + 1]].second < rmq[primaAparitie[yFolosit] - (1 << putere2Max[primaAparitie[yFolosit] - primaAparitie[xFolosit] + 1]) + 1][putere2Max[primaAparitie[yFolosit] - primaAparitie[xFolosit] + 1]].second)
                stramosComun = rmq[primaAparitie[xFolosit]][putere2Max[primaAparitie[yFolosit] - primaAparitie[xFolosit] + 1]].first;
            else
                stramosComun = rmq[primaAparitie[yFolosit] - (1 << putere2Max[primaAparitie[yFolosit] - primaAparitie[xFolosit] + 1]) + 1][putere2Max[primaAparitie[yFolosit] - primaAparitie[xFolosit] + 1]].first;

            int solCrt = min(minimLant(xFolosit, stramosComun), minimLant(yFolosit, stramosComun));
            if (solCrt == INT_MAX)
                solCrt = 0;

            sol.push_back(solCrt);
        }
        else
            sol.push_back(0);

        xCrt = ((long long)xCrt * a + (long long)yCrt * b) % n + 1;
        yCrt = ((long long)yCrt * c + (long long)sol[sol.size() - 1] * d) % n + 1;
    }

    for (int i = sol.size() - p; i < sol.size(); i++)
        out << sol[i] << '\n';

    return 0;
}