Cod sursa(job #3304271)

Utilizator Mihai_OctMihai Octavian Mihai_Oct Data 22 iulie 2025 11:53:11
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <bits/stdc++.h>

using namespace std;

#define ST_DIO 0
#if ST_DIO
    #define fin cin
    #define fout cout
#else
    ifstream fin("atac.in");
    ofstream fout("atac.out");
#endif  // ST_DIO

const int LOG_MAX = 15;
struct Muchie {
    int vec, cost;
};
int n, m, p, i, x, y, z, a, b, c, d;
vector<Muchie> gr[32002];

int rmq[LOG_MAX + 2][32002];
int tata[LOG_MAX + 2][32002];
int niv[32002];

static inline void DFS(int nod = 1, int tataNod = 0, int cost = 0, int nivNod = 1) {
    tata[0][nod] = tataNod;
    rmq[0][nod] = cost;
    niv[nod] = nivNod;

    for(Muchie urm : gr[nod]) {
        if(urm.vec != tataNod) DFS(urm.vec, nod, urm.cost, 1 + nivNod);
    }
}

static inline int LCA(int x, int y) {
    if(x == y) return 0;

    if(niv[x] < niv[y]) swap(x, y);

    int costMi = INT_MAX;
    int dif = niv[x] - niv[y];
    for(int put = LOG_MAX - 1; put >= 0; put--) {
        if(dif >> put & 1) {
            costMi = min(costMi, rmq[put][x]);
            x = tata[put][x];
        }
    }

    if(x == y) return costMi;

    for(int put = LOG_MAX - 1; put >= 0; put--) {
        if(tata[put][x] != tata[put][y]) {
            costMi = min({costMi, rmq[put][x], rmq[put][y]});
            x = tata[put][x];
            y = tata[put][y];
        }
    }
    costMi = min({costMi, rmq[0][x], rmq[0][y]});
    return costMi;
}

int main() {
    if(ST_DIO) ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    fin >> n >> m >> p;
    for(i = 2; i <= n; i++) {
        int x, c;
        fin >> x >> c;
        gr[i].push_back({x, c});
        gr[x].push_back({i, c});
    }

    DFS();


    for(int put = 1; put < LOG_MAX; put++) {
        for(i = 1; i <= n; i++) tata[put][i] = tata[put - 1][tata[put - 1][i]];
        for(i = 1; i <= n; i++)  rmq[put][i] = min(rmq[put - 1][i], rmq[put - 1][tata[put - 1][i]]);
    }


    fin >> x >> y >> a >> b >> c >> d;

    for(i = 1; i <= m; i++) {
        z = LCA(x, y);

        if(m - p + 1 <= i) fout << z << "\n";

        x = 1LL * (x * a + b * y) % n + 1;
        y = 1LL * (y * c + z * d) % n + 1;
    }

    return 0;
}