Cod sursa(job #3331545)

Utilizator MihneaStoicaMihnea Teodor Stoica MihneaStoica Data 29 decembrie 2025 09:41:46
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.04 kb
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;

#if 0
#define int ll
#define uint ull
#endif

/**
 * Problem: Atac
 * URL: https://infoarena.ro/problema/atac
 * TL: 400 ms
 * ML: 64 MB
 *
 * Good Luck!
*/

void preinit() {
}

const int LOG_MAX = 16;

vector<vector<pair<int, int>>> adj;
vector<vector<int>> up, mn;
vector<int> depth;

void dfs(int nod, int tt = 0) {
    for (auto x : adj[nod]) {
        if (x.first != tt) {
            depth[x.first] = depth[nod] + 1;
            up[0][x.first] = nod;
            mn[0][x.first] = x.second;
            dfs(x.first, nod);
        }
    }
}

void tc() {
    int n, m, p;
    cin >> n >> m >> p;
    adj.resize(n + 1);
    depth.resize(n + 1);
    up.resize(LOG_MAX, vector<int>(n + 1));
    mn.resize(LOG_MAX, vector<int>(n + 1, INT32_MAX));

    for (int i = 2; i <= n; i++) {
        int u, v;
        cin >> u >> v;
        adj[i].push_back({u, v});
        adj[u].push_back({i, v});
        // cout << i << " " << u << " " << v << '\n';
    }
    // cout << '\n';

    dfs(1);

    // for (int i = 0; i < 2; i++) {
    //     for (int j = 1; j <= n; j++) {
    //         cout << up[i][j] << " ";
    //     }
    //     cout << '\n';
    // }
    // cout << '\n';

    // for (int i = 0; i < 2; i++) {
    //     for (int j = 1; j <= n; j++) {
    //         cout << mn[i][j] << " ";
    //     }
    //     cout << '\n';
    // }
    // cout << '\n';

    for (int i = 1; i < LOG_MAX; i++) {
        for (int j = 1; j <= n; j++) {
            up[i][j] = up[i - 1][up[i - 1][j]];
            mn[i][j] = min(mn[i - 1][up[i - 1][j]], mn[i - 1][j]);
        }
    }

    auto query = [&](int u, int v) -> int {
        int ans = INT32_MAX;

        if (depth[u] < depth[v])
            swap(u, v);

        for (int i = LOG_MAX - 1; i >= 0; i--) {
            if (depth[u] > depth[v]) {
                if ((1 << i) <= depth[u] - depth[v]) {
                    ans = min(ans, mn[i][u]);
                    u = up[i][u];
                }
            } else if (u != v) {
                if (up[i][u] != up[i][v]) {
                    ans = min({ans, mn[i][u], mn[i][v]});
                    u = up[i][u];
                    v = up[i][v];
                }
            } else
                return ans;
        }
        return min({ans, mn[0][u], mn[0][v]});
    };

    int x, y, a, b, c, d;
    cin >> x >> y >> a >> b >> c >> d;
    for (int i = 1; i <= m; i++) {
        int z = query(x, y);
        if (i >= m - p + 1) {
            cout << z << '\n';
        }
        int xx = (x * a + y * b) % n + 1, yy = (y * c + z * d) % n + 1;
        x = xx;
        y = yy;
    }
}

#define MTC 0
#define FIO 1
#define FN "atac"

signed main() {
#if FIO == 1 && !defined(LOCAL)
    (void)freopen(FN ".in", "r", stdin);
    (void)freopen(FN ".out", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    preinit();
#if MTC == 1
    signed tt;
    cin >> tt;
    while (tt--) tc();
#else
    tc();
#endif
    return 0;
}