Cod sursa(job #2864391)

Utilizator cezar.balutaCezar Baluta cezar.baluta Data 7 martie 2022 20:35:33
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.42 kb
/*
                         __
                   _.--""  |
    .----.     _.-'   |/\| |.--.
    |    |__.-'   _________|  |_)  _______________
    |  .-""-.""""" ___,    `----'"))   __   .-""-.""""--._
    '-' ,--. `    |Cezar| .---.       |:.| ' ,--. `      _`.
     ( (    ) ) __|  7  |__\\|// _..-- \/ ( (    ) )--._".-.
      . `--' ;\__________________..--------. `--' ;--------'
       `-..-'                               `-..-'
*/
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int N = 32e3 + 5;
const int LOG  = 16;

int up[N][LOG];
int rmq[N][LOG];
int nivel[N];
int log_2[N];
vector<int>v[N];

void dfs(int x, int tata){
    nivel[x] = nivel[tata] + 1;
    for(auto y:v[x]){
        if(y!=tata){
            dfs(y,x);
        }
    }
}

int bomb(int x, int y){
    if(x == y)
        return 0;
    int rez = (1<<30);
    if(nivel[x]<nivel[y])
        swap(x,y);

    for(int i =log_2[nivel[x]-nivel[y]]; i>=0;i--){
        if(nivel[x] == nivel[y])
            break;
        if(nivel[x] - (1<<i) >= nivel[y]){
            rez = min(rez,rmq[x][i]);
            x = up[x][i];
        }
    }

    if(x == y)
        return rez;
        int new_x, new_y;
        for (int i = log_2[nivel[x]]; i >= 0; i--) {
            new_x = up[x][i];
            new_y = up[y][i];
            if (new_x != new_y) {
                rez = min(rez, rmq[x][i]);
                rez = min(rez, rmq[y][i]);
                x = new_x;
                y = new_y;
            }
        }
    rez = min(rez, rmq[x][0]);
    rez = min(rez, rmq[y][0]);
    return rez;
}

int main() {
    ifstream in("atac.in");
    ofstream out("atac.out");
    int n,m,p;
    in>>n>>m>>p;

    for(int i=2;i<=n;i++)
        log_2[i] = log_2[i/2] + 1;

    for(int i = 2;i<=n;i++){
        in>>up[i][0];
        v[up[i][0]].push_back(i);
        in>>rmq[i][0];
    }

    int x,y,A,B,C,D;
    in>>x>>y>>A>>B>>C>>D;
    up[1][0] = 1;
    dfs(1,1);
    for(int i = 1;i<LOG;i++){
        for(int j=1;j<=n;j++){
            up[j][i] = up[up[j][i-1]][i-1];
            rmq[j][i] = min(rmq[j][i-1],rmq[up[j][i-1]][i-1]);
        }
    }
    for(int i=0;i<m-p;i++){
        int z;
        z = bomb(x,y);
        //out<<z<<'\n';
        x = (x*A + y*B) % n + 1;
        y = (y*C + z*D) % n + 1;
    }
    for(int i=0;i<p;i++){
        int z;
        z = bomb(x,y);
        out<<z<<'\n';
        x = (x*A + y*B) % n + 1;
        y = (y*C + z*D) % n + 1;
    }
    return 0;
}