Cod sursa(job #3177711)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 29 noiembrie 2023 19:36:55
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <bits/stdc++.h>
/// reimplementez
using namespace std;

const int max_size = 32e3 + 1, rmax = 16, INF = 2e9 + 1;

struct str{
    int x, mn;
};

int lvl[max_size], lg[max_size], viz[max_size];
str t[rmax][max_size];
vector <pair <int, int>> mc[max_size];

void dfs (int nod)
{
    viz[nod] = 1;
    for (auto f : mc[nod])
    {
        if (viz[f.first])
        {
            continue;
        }
        lvl[f.first] = lvl[nod] + 1;
        t[0][f.first].x = nod;
        t[0][f.first].mn = f.second;
        for (int e = 1; e < rmax; e++)
        {
            t[e][f.first].x = t[e - 1][t[e - 1][f.first].x].x;
            t[e][f.first].mn = min(t[e - 1][f.first].mn, t[e - 1][t[e - 1][f.first].x].mn);
        }
        dfs(f.first);
    }
}

int lca (int x, int y)
{
    if (x == y)
    {
        return 0;
    }
    if (lvl[x] > lvl[y])
    {
        swap(x, y);
    }
    int ans = INF, dif = lvl[y] - lvl[x];
    for (int e = 0; e < rmax; e++)
    {
        if ((dif & (1 << e)) != 0)
        {
            ans = min(ans, t[e][y].mn);
            y = t[e][y].x;
        }
    }
    if (x == y)
    {
        return ans;
    }
    for (int e = lg[lvl[x]]; e >= 0; e--)
    {
        if (t[e][x].x != t[e][y].x)
        {
            ans = min(ans, t[e][x].mn);
            ans = min(ans, t[e][y].mn);
            x = t[e][x].x;
            y = t[e][y].x;
        }
    }
    return min(ans, min(t[0][x].mn, t[0][y].mn));
}

signed main ()
{
#ifdef LOCAL
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#else
    freopen("atac.in", "r", stdin);
    freopen("atac.out", "w", stdout);
#endif // LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q, p;
    cin >> n >> q >> p;
    for (int i = 2; i <= n; i++)
    {
        int x, c;
        cin >> x >> c;
        mc[x].push_back({i, c});
        mc[i].push_back({x, c});
        lg[i] = lg[i / 2] + 1;
    }
    for (int e = 0; e < rmax; e++)
    {
        t[e][1].x = 1;
        t[e][1].mn = INF;
    }
    int x, y, a, b, c, d;
    cin >> x >> y >> a >> b >> c >> d;
    dfs(1);
    while (q--)
    {
        int ans = lca(x, y);
        x = (x * a + y * b) % n + 1;
        y = (y * c + ans * d) % n + 1;
        if (q < p)
        {
            cout << ans << '\n';
        }
    }
    return 0;
}