Cod sursa(job #2847455)

Utilizator MocalinnoMoca Andrei Catalin Mocalinno Data 10 februarie 2022 20:20:02
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int INF(1e9), NMAX(1e5 + 5), LMAX(17);
int t[NMAX][LMAX], r[NMAX][LMAX], lvl[NMAX], l2[NMAX], p2[LMAX];
vector<pair<int, int>> g[NMAX];
inline void DFS(int const& x = 1) {
    for (int i = 1; i < LMAX; ++i)
        t[x][i] = t[t[x][i - 1]][i - 1];
    for (int i = 1; i < LMAX; ++i)
        r[x][i] = min(r[x][i - 1], r[t[x][i - 1]][i - 1]);
    for (pair<int, int> const& P : g[x]) {
        int y, w;
        tie(y, w) = P;
        if (y == t[x][0])
            continue;
        lvl[y] = lvl[x] + 1;
        t[y][0] = x;
        r[y][0] = w;
        DFS(y);
    }
}
inline int Query(int const& a, int const& b) {
    int x = a, y = b, res = INF;
    if (lvl[x] < lvl[y])
        swap(x, y);
    for (int i = l2[lvl[x] - lvl[y] + 1]; i >= 0; --i)
        if (lvl[x] - p2[i] >= lvl[y]) {
            res = min(res, r[x][i]);
            x = t[x][i];
        }
    if (x == y)
        return res;
    for (int i = l2[lvl[x] + 1]; i >= 0; --i)
        if (t[x][i] != t[y][i]) {
            res = min({res, r[x][i], r[y][i]});
            x = t[x][i];
            y = t[y][i];
        }
    res = min({res, r[x][0], r[y][0]});
    return res;
}
inline void Init() {
    for (int i = 2; i < NMAX; ++i)
        l2[i] = l2[i / 2] + 1;
    p2[0] = 1;
    for (int i = 1; i < LMAX; ++i)
        p2[i] = p2[i - 1] * 2;
    for (int i = 0; i < NMAX; ++i)
        for (int j = 0; j < LMAX; ++j)
            r[i][j] = INF;
}
int main() {
    Init();
    int n, m, p;
    fin >> n >> m >> p;
    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);
    }
    DFS();
    int x, y, a, b, c, d;
    fin >> x >> y >> a >> b >> c >> d;
    while (m--) {
        int z = Query(x, y);
        if (z == INF) z = 0;
        if (m < p) fout << z << '\n';
        x = (x * a + y * b) % n + 1;
        y = (y * c + z * d) % n + 1;
    }
    return 0;
}