Cod sursa(job #3207213)

Utilizator amcbnCiobanu Andrei Mihai amcbn Data 25 februarie 2024 15:02:01
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <bits/stdc++.h>
using namespace std;
const char nl = '\n';
const char sp = ' ';
const int inf = 0x3f3f3f3f;
const int mod = 30011;
const char out[2][4]{ "NO", "YES" };
#define all(a) a.begin(), a.end()
using ll = long long;
ifstream fin("atac.in");
ofstream fout("atac.out");

const int nmax = 32000;
const int lgmax = 15;
int n, m, p;
vector<pair<int, int>> g[nmax + 5];
int depth[nmax + 5]{ 0 };
int t[lgmax][nmax + 5]{ 0 };
int rmq[lgmax][nmax + 5]{ 0 };

void compute(int u, int p = -1) {
    for (auto& e : g[u]) {
        int v = e.first, w = e.second;
        if (v == p) {
            continue;
        }
        depth[v] = depth[u] + 1;
        t[0][v] = u;
        rmq[0][v] = w;
        for (int p = 1; p < lgmax; ++p) {
            if (t[p - 1][v] == 0 || t[p - 1][t[p - 1][v]] == 0) {
                break;
            }
            t[p][v] = t[p - 1][t[p - 1][v]];
            rmq[p][v] = min(rmq[p - 1][v], rmq[p - 1][t[p - 1][v]]);
        }
        compute(v, u);
    }
}

pair<int, int> kth(int x, int k) {
    // returns the k-th ancestor of x and the minimum edge of the path between x and it's ancestor
    if (k == 0) {
        return { x, inf };
    }
    pair<int, int> res{ x, inf };
    for (int bit = 0; (1 << bit) <= k; ++bit) {
        if ((k >> bit) & 1) {
            res.second = min(res.second, rmq[bit][res.first]);
            res.first = t[bit][res.first];
        }
    }
    return res;
}

int query(int x, int y) {
    if (x == y) {
        return 0;
    }
    if (depth[x] > depth[y]) { // x sa fie mai sus decat y
        swap(x, y);
    }
    int ans = inf;
    if (depth[x] != depth[y]) { // x si y sa fie la acelasi nivel
        tie(y, ans) = kth(y, depth[y] - depth[x]);
    }
    if (x == y) {
        return ans;
    }
    for (int p = lgmax - 1; p >= 0; --p) {
        if (t[p][x] != t[p][y]) { // urc nodurile simultan
            ans = min(ans, min(rmq[p][x], rmq[p][y]));
            x = t[p][x];
            y = t[p][y];
        }
    }
    return min(ans, min(rmq[0][x], rmq[0][y]));
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    fin >> n >> m >> p;
    for (int i = 2; i <= n; ++i) {
        int j, w;
        fin >> j >> w;
        g[i].push_back({ j, w });
        g[j].push_back({ i, w });
    }
    compute(1);
    ll x, y, a, b, c, d;
    fin >> x >> y >> a >> b >> c >> d;
    for (int q = 1; q <= m; ++q) {
        ll z = query(x, y);
        if (m - q + 1 <= p) {
            fout << z << nl;
        }
        x = (a * x + b * y) % n + 1;
        y = (c * y + d * z) % n + 1;
    }
}