Cod sursa(job #3176930)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 28 noiembrie 2023 08:02:45
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <bits/stdc++.h>

using namespace std;

struct str{
    long long x, c;
};

const long long max_size = 32e3 + 1, rmax = 17, INF = 1e9 + 1;

long long lvl[max_size], lg[max_size];
str t[rmax][max_size];
vector <str> mc[max_size];

void dfs (long long nod, long long par, long long cost)
{
  //  out << par << " " << nod << '\n';
    t[0][nod].x = par;
    t[0][nod].c = cost;
    lvl[nod] = lvl[par] + 1;
    for (auto f : mc[nod])
    {
        if (f.x != par)
        {
            dfs(f.x, nod, f.c);
        }
    }
}

str anc (long long x, long long ord)
{
    str ans = {x, INF};
    long long e = 0;
    while (ord > 0)
    {
        if (ord % 2 == 1)
        {
            ans.x = t[e][x].x;
            ans.c = min(t[e][x].c, ans.c);
            x = t[e][x].x;
        }
        e++;
        ord /= 2;
    }
    return ans;
}

long long lca (long long x, str ry)
{
    long long mx1 = INF, mx2 = ry.c, y = ry.x;
    long long e = lg[lvl[x]];
    while (e >= 0)
    {
        if (t[e][x].x != t[e][y].x)
        {
            mx1 = min(t[e][x].c, mx1);
            x = t[e][x].x;
            mx2 = min(t[e][y].c, mx2);
            y = t[e][y].x;
        }
        e--;
    }
    return min(min(mx1, mx2), min(t[0][x].c, t[0][y].c));
}

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
    long long n, m, q;
    cin >> n >> m >> q;
    for (long long i = 2; i <= n; i++)
    {
        long long x, c;
        cin >> x >> c;
        mc[x].push_back({i, c});
        mc[i].push_back({x, c});
    }
    dfs(1, 0, 0);
    for (long long e = 1; e < rmax; e++)
    {
        for (long long i = 1; i <= n; i++)
        {
            t[e][i].x = t[e - 1][t[e - 1][i].x].x;
            t[e][i].c = min(t[e - 1][i].c, t[e - 1][t[e - 1][i].x].c);
        }
    }
    for (long long i = 2; i <= n; i++)
    {
        lg[i] = lg[i /2] + 1;
    }
    long long x, y, a, b, c, d;
    cin >> x >> y >> a >> b >> c >> d;
    while (m--)
    {
        long long ans = INF;
        if (lvl[x] > lvl[y])
        {
            swap(x, y);
        }
        str ry = anc(y, lvl[y] - lvl[x]);
        if (ry.x == x)
        {
            ans = ry.c;
        }
        else
        {
            ans = lca(x, ry);
        }
        if (ans == INF)
        {
            ans = 0;
        }
        if (m < q)
        {
            cout << ans << '\n';
        }
        long long xp = (x * a + y * b) % n + 1, yp = (y * c + ans * d) % n + 1;
        x = xp;
        y = yp;
    }
    return 0;
}