Cod sursa(job #2846990)

Utilizator MocalinnoMoca Andrei Catalin Mocalinno Data 9 februarie 2022 22:31:37
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.85 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using VP = vector<PII>;
using VVP = vector<VP>;
class SegTree {
public:
    SegTree(VI const& v) {
        for (N = 1; N < static_cast<int>(v.size()); N *= 2);
        tree = VI(2 * N, 1e9);
        for (int i = 0; i < static_cast<int>(v.size()); ++i)
            tree[N + i] = v[i];
        for (int x = N - 1; x > 0; --x)
            tree[x] = min(tree[2 * x], tree[2 * x + 1]);
    }
    inline void Update(int const& pos, int const& val) {
        int p = pos + N;
        tree[p] = val;
        for (p /= 2; p; p /= 2)
            tree[p] = min(tree[2 * p], tree[2 * p + 1]);
    }
    inline int Query(int const& st, int const& dr) const {
        int l = st + N, r = dr + N, ans = 1e9;
        while (l <= r) {
            ans = min({ans, tree[l], tree[r]});
            l = (l + 1) / 2;
            r = (r - 1) / 2;
        }
        return ans;
    }
private:
    int N;
    VI tree;
};
class HeavyPath {
public:
    HeavyPath(int const& _N = 0)
        : N(_N), g(N + 1), t(N + 1), h(N + 1), nr(N + 1), pId(N + 1), pos(N + 1) {}
    inline void SetValues(VI const& _v) {
        v = _v;
    }
    inline void AddEdge(int const& x, int const& y) {
        g[x].emplace_back(y);
        g[y].emplace_back(x);
    }
    inline void BuildHP() {
        DFS();
        for (VI const& path : paths) {
            VI values;
            for (int const& x : path)
                values.emplace_back(v[x]);
            st.emplace_back(SegTree(values));
        }
    }
    inline int Query(int const& _x, int const& _y) const {
        int x = _x, y = _y;
        if (pId[x] == pId[y]) {
            if (pos[x] > pos[y])
                swap(x, y);
            return st[pId[x]].Query(pos[x], pos[y]);
        }
        if (h[paths[pId[x]].back()] < h[paths[pId[y]].back()])
            swap(x, y);
        int r1 = st[pId[x]].Query(pos[x], static_cast<int>(paths[pId[x]].size()) - 1);
        int r2 = Query(t[paths[pId[x]].back()], y);
        return min(r1, r2);
    }
    inline void Update(int const& x, int const& val) {
        v[x] = val;
        st[pId[x]].Update(pos[x], val);
    }
private:
    inline void DFS(int const& x = 1) {
        int hs = 0;
        nr[x] = 1;
        for (int const& y : g[x]) {
            if (y == t[x])
                continue;
            t[y] = x;
            h[y] = h[x] + 1;
            DFS(y);
            nr[x] += nr[y];
            if (nr[y] > nr[hs])
                hs = y;
        }
        if (!hs) {
            pId[x] = static_cast<int>(paths.size());
            paths.emplace_back(VI());
        }
        else pId[x] = pId[hs];

        pos[x] = static_cast<int>(paths[pId[x]].size());
        paths[pId[x]].emplace_back(x);
    }
    int N;
    VVI g, paths;
    VI v, t, h, nr, pId, pos;
    vector<SegTree> st;
};
VI v;
VVP g;
inline void DFS(int const& x = 1, int const& dad = 0) {
    for (pair<int, int> const& P : g[x]) {
        int y, w;
        tie(y, w) = P;
        if (y == dad)
            continue;
        v[y] = w;
        DFS(y, x);
    }
}
int main() {
    int n, m, p;
    fin >> n >> m >> p;
    HeavyPath HP(n);
    g = VVP(n + 1);
    for (int i = 2; i <= n; ++i) {
        int j, w;
        fin >> j >> w;
        g[i].emplace_back(j, w);
        g[j].emplace_back(i, w);
        HP.AddEdge(i, j);
    }
    v = VI(n + 1, 1e9);
    DFS();
    HP.SetValues(v);
    HP.BuildHP();
    int x, y, a, b, c, d;
    fin >> x >> y >> a >> b >> c >> d;
    while (m--) {
        int z = HP.Query(x, y);
        if (m < p)
            fout << z << '\n';
        x = (x * a + y * b) % n + 1;
        y = (y * c + z * d) % n + 1;
    }
    return 0;
}