Cod sursa(job #2921549)

Utilizator Iordache_CezarIordache Cezar Iordache_Cezar Data 31 august 2022 16:52:14
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.72 kb
#include <bits/stdc++.h>
#define NMAX 32008

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

int n, m, p;
int X, Y, Z, A, B, C, D;
vector < pair <int, int> > G[NMAX], euler;
int first[NMAX*2], dp[NMAX*2][50], logg[NMAX*2], h[NMAX], dp2[NMAX*2][50], nodd[NMAX], str[NMAX*2][50];

void citire();
void DFS(int nod, int tata);
void DFS_euler(int nod, int tata);
void RMQ();
void logaritm();
int query(int x, int y);

int main()
{
    citire();
    logaritm();
    h[0] = -1;
    DFS_euler(1, 0);
    RMQ();
    for (int i = 1; i <= m; i++)
    {
        int min1 = 1e9, min2 = 1e9, min3 = 1e9, min4 = 1e9;
        int lca = query(X, Y);
        lca = euler[lca].first;
        int lg = h[X] - h[lca];
        if (lg)
        {
            int sz = logg[lg];
            min1 = dp2[X][sz];
            int nr = lg - (1<<sz);
            int stramos = X;
            while (nr)
            {
                int sz2 = logg[nr];
                stramos = str[stramos][sz2];
                nr = nr - (1<<sz2);
            }
            min2 = dp2[stramos][sz];
        }

        lg = h[Y] - h[lca];
        if (lg)
        {
            int sz = logg[lg];
            min3 = dp2[Y][sz];
            int nr = lg - (1<<sz);
            int stramos = Y;
            while (nr)
            {
                int sz2 = logg[nr];
                stramos = str[stramos][sz2];
                nr = nr - (1<<sz2);
            }
            min4 = dp2[stramos][sz];
        }

        Z = min(min1, min(min2, min(min3, min4)));
        if (Z == 1e9)
            Z = 0;

        if (i >= m - p + 1)
            fout << Z << '\n';
        X = (X*A + Y*B) % n + 1;
        Y = (Y*C + Z*D) % n + 1;
    }
    return 0;
}

void citire()
{
    int x, y;
    fin >> n >> m >> p;
    for (int i = 2; i <= n; i++)
    {
        fin >> x >> y;
        G[x].push_back({i, y});
        G[i].push_back({x, y});
    }
    fin >> X >> Y >> A >> B >> C >> D;
}

void DFS_euler(int nod, int tata)
{
    first[nod] = euler.size();
    h[nod] = h[tata] + 1;
    nodd[h[nod]] = nod;
    euler.push_back({nod, h[nod]});
    for (auto fiu : G[nod])
        if (fiu.first != tata)
        {
            if (fiu.first == 6)
                int ok = 1;
            dp2[fiu.first][0] = fiu.second;
            str[fiu.first][0] = nod;
            for (int j = 1; h[nod]+1-(1<<j)>=0; j++)
            {
                int stramos = nodd[h[nod]+1-(1<<(j-1))];
                dp2[fiu.first][j] = min(dp2[fiu.first][j-1], dp2[stramos][j-1]);
                str[fiu.first][j] = str[stramos][j-1];
            }
            DFS_euler(fiu.first, nod);
            euler.push_back({nod, h[nod]});
        }
}

void RMQ()
{
    int len = euler.size();
    for (int i = 0; i < len; i++)
        dp[i][0] = i;

    for (int j = 1; (1 << j) <= len; j++)
        for (int i = 0; i + (1<<j) <= len; i++)
        {
            int poz1 = dp[i][j-1];
            int min1 = euler[poz1].second;
            int poz2 = dp[i+(1<<(j-1))][j-1];
            int min2 = euler[poz2].second;
            if (min1 < min2)
                dp[i][j] = poz1;
            else
                dp[i][j] = poz2;
        }
}

void logaritm()
{
    logg[1] = 0;
    for (int i = 2; i <= 2 * n; i++)
        logg[i] = 1 + logg[i/2];
}

int query(int x, int y)
{
    int l = first[x];
    int r = first[y];
    if (l > r)
        swap(l, r);
    int lg = r - l + 1;
    int sz = logg[lg];

    int poz1 = dp[l][sz];
    int min1 = euler[poz1].second;
    int poz2 = dp[r+1-(1<<(sz))][sz];
    int min2 = euler[poz2].second;
    if (min1 < min2)
        return poz1;
    else
        return poz2;
}