Cod sursa(job #2648125)

Utilizator Tudor06MusatTudor Tudor06 Data 8 septembrie 2020 19:15:26
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.76 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 32000;
const int LOGNMAX = 15;
const int INF = 1e9 + 1;

int RMQ[LOGNMAX + 1][2 * NMAX][2];
int log[2 * NMAX + 1];
int codification[NMAX];
int decodification[NMAX];
int first_appearance[NMAX];

struct edge {
    int children;
    int value;
};
vector <edge> edges[NMAX + 1];

int index, new_node;

void first_row( int current_node ) { /// first_row( 0, INF );
    codification[current_node] = new_node;
    decodification[new_node] = current_node;
    RMQ[0][index][0] = new_node;
    new_node ++;
    index ++;
    for ( auto x : edges[current_node] ) {
        RMQ[0][index][1] = x.value;
        first_row( x.children );
        RMQ[0][index][1] = x.value;
        RMQ[0][index++][0] = current_node;
    }
}
void calculate_log( int n ) {
    for ( int i = 2; i <= 2 * n; i ++ ) {
        log[i] = log[i / 2] + 1;
    }
}

void build_RMQ( int n ) {
    int i, j, x;
    for ( i = 1; ( 1 << i ) <= 2 * n - 1; i ++ ) {
        for ( j = 0; j + ( 1 << i ) < 2 * n; j ++ ) {
            RMQ[i][j][1] = min( RMQ[i - 1][j][1], RMQ[i - 1][j + ( 1 << ( i - 1 ) )][1] );
        }
    }
}
int ans( int i, int j, int x ) {
    return ( min( RMQ[log[j - i + 1]][i][x], RMQ[log[j - i + 1]][j - ( 1 << ( log[j - i + 1] ) ) + 1][x] ) );
}
void calculate_appearances( int n ) {
    int i;
    for ( i = 0; i < n; i ++ )
        first_appearance[i] = -1;
    for ( i = 0; i < 2 * n - 1; i ++ ) {
        if ( first_appearance[decodification[RMQ[0][i][0]]] == -1 )
            first_appearance[decodification[RMQ[0][i][0]]] = i;
    }
}
int main() {
    ifstream fin( "atac.in" );
    ofstream fout( "atac.out" );
    int n, m, p, i, j, x, y, node, val, a, b, c, d, length, st, dr, answer;
    fin >> n >> m >> p;
    for ( i = 0; i < n - 1; i ++ ) {
        fin >> node >> val;
        edges[node - 1].push_back( { i + 1, val } );
    }
    calculate_log( n );
    first_row( 0 );
    RMQ[0][0][1] = INF;
    build_RMQ( n );
//    for ( i = 0; ( 1 << i ) <= 2 * n - 1; i ++ ) {
//        for ( j = 0; j + ( 1 << i ) < 2 * n; j ++ ) {
//            cout << RMQ[i][j][1] << ' ';
//        }
//        cout << endl;
//    }
    calculate_appearances( n );
    fin >> x >> y >> a >> b >> c >> d;
    for ( i = 0; i < m; i ++ ) {
        st = first_appearance[codification[x - 1]];
        dr = first_appearance[codification[y - 1]];
        if ( st > dr )
            swap( dr, st );
        if ( dr == st )
            answer = 0;
        else
            answer = ans( st, dr, 1 );
        if ( i >= m - p )
            fout << answer << '\n';
        x = ( x * a + y * b ) % n + 1;
        y = ( y * c + answer * d ) % n + 1;
    }
    return 0;
}