Cod sursa(job #3131212)

Utilizator Theodor17Pirnog Theodor Ioan Theodor17 Data 19 mai 2023 15:50:38
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream cin("atac.in");
ofstream cout("atac.out");

const int NMAX = 32e3;
const int inf = 2e9;

vector <pair <int, int>> g[NMAX + 1];
int e[2 * NMAX + 1], nivel[NMAX + 1], r[21][2 * NMAX + 1], poz[NMAX + 1], lg2[NMAX + 1], ne;
int cost[NMAX + 1];
bool viz[NMAX + 1];

void dfs(int x){

    e[++ne] = x;
    poz[x] = ne;
    viz[x] = 1;

    for(auto y : g[x]){

        if(viz[y.first] == 1)
            continue;

        nivel[y.first] = 1 + nivel[x];

        dfs(y.first);
        e[++ne] = x;

        cost[x] = min(cost[x], min(cost[y.first], y.second));

    }

}

int lca(int x, int y){

    int st = poz[x], dr = poz[y];
    if(st > dr)
        swap(st, dr);

    int l = lg2[dr - st + 1];
    int p = (1 << l);
    x = r[l][st + p - 1];
    y = r[l][dr];
    if(nivel[x] > nivel[y])
        x = y;

    return x;
}

int atac(int x, int y){

    return cost[lca(x, y)];

}

int main(){

    int n = 0, m = 0, p = 0;
    cin >> n >> m >> p;

    cost[1] = inf;
    for(int i = 2; i <= n; i++){

        int x = 0, c = 0;
        cin >> x >> c;

        g[x].push_back({i, c});
        g[i].push_back({x, c});

        cost[i] = inf;

    }

    dfs(1);

    lg2[0] = -1;
    for(int i = 1; i <= ne; i++){

        lg2[i] = 1 + lg2[i >> 1];
        r[0][i] = e[i];

    }

    for(int i = 1; (1 << i) <= ne; i++){
        for(int j = (1 << i); j <= ne; j++){

            r[i][j] = r[i - 1][j];
            int p = (1 << (i - 1));

            if(nivel[r[i - 1][j - p]] < nivel[r[i - 1][j]])
                r[i][j] = r[i - 1][j - p];

        }
    }

    int x = 0, y = 0, a = 0, b = 0, c = 0, d = 0;
    cin >> x >> y >> a >> b >> c >> d;

    for(int i = 0; i < m; i++){

        int z = atac(x, y);

        if(x == y)
            z = 0;

        //cout << "perechea este " << x << " " << y << "\n";


        if(i >= m - p){

            cout << z << "\n";

        }

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

    }

    return 0;
}