Cod sursa(job #2836942)

Utilizator Stefan_DomuncoStefan Domunco Stefan_Domunco Data 21 ianuarie 2022 11:26:45
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 32e3 + 5, MMAX = 5e5 + 4;

int A, B, C, D, x, y;
int n, q, p, cost[2 * NMAX + 5];
int peuler[2 * NMAX + 5], nrpeuler = 0;
int rmq[2 * NMAX + 5][22], firstPos[NMAX];
int ans[MMAX];

vector <int> g[NMAX];
map < pair <int, int>, int > costMuchii;
bitset <NMAX> viz;

inline void citire()
{
    memset(firstPos, 0, sizeof(firstPos));
    memset(cost, 0, sizeof(cost));
    memset(peuler, 0, sizeof(peuler));

    fin >> n >> q >> p;
    for(int i = 2; i <= n; ++i)
    {
        fin >> x >> y;
        costMuchii[{min(x, i), max(x, i)}] = y;
        g[i].push_back(x);
        g[x].push_back(i);
    }

    fin >> x >> y >> A >> B >> C >> D;
}

inline int newX(int X, int Y)
{
    return (X * A + Y * B) % n + 1;
}

inline int newY(int Y, int Z)
{
    return (Y * C + Z * D) % n + 1;
}

void DFS(int node, pair <int, int> aa)
{
    if(firstPos[node] == 0)
        firstPos[node] = nrpeuler + 1;

    viz[node] = 1;

    for(auto &it: g[node])
    {
        if(viz[it] == 1)
            continue;

        peuler[++nrpeuler] = costMuchii[{min(node, it), max(node, it)}];
        DFS(it, {min(node, it), max(node, it)});
    }

    peuler[++nrpeuler] = costMuchii[aa];
}

void build_rmq()
{
    int i, j;

    for(i = 1; i <= nrpeuler; ++i)
        rmq[i][0] = peuler[i];

    for(j = 1; 1 << j <= nrpeuler; ++j)
    {
        for(i = 1; i + (1 << j) - 1 <= nrpeuler; ++i)
            rmq[i][j] = min(rmq[i][j-1], rmq[i + (1 << (j-1))][j-1]);

    }
}

inline int solve_query()
{
    int xx, yy;
    xx = x;
    yy = y;

    if(firstPos[xx] > firstPos[yy])
        swap(xx, yy);

    int lung = log2(firstPos[yy] - firstPos[xx] + 1);

    return min(rmq[firstPos[xx]][lung], rmq[firstPos[yy] - (1 << lung) + 1][lung]);
}

int main()
{
    citire();
    costMuchii[{0, 0}] = 0;
    DFS(1, {0, 0});
    build_rmq();

    int xx, yy, i = 0, qq = q;
    while(q)
    {
        --q;
        ans[++i] = solve_query();
        xx = x;
        yy = y;
        x = newX(xx, yy);
        y = newY(yy, ans[i]);
    }

    for(i = qq - p + 1; i <= qq; ++i)
        fout << ans[i] << '\n';

//    for(int j = 0; 1 << j <= nrpeuler; ++j)
//    {
//        for(int i = 1; i + (1 << j) - 1 <= nrpeuler; ++i)
//            fout << rmq[i][j] << ' ';
//        fout << '\n';
//    }
//    for(int i = 1; i <= nrpeuler; ++i)
//        fout << peuler[i] << ' ';

    return 0;
}