Cod sursa(job #2648291)

Utilizator Tudor06MusatTudor Tudor06 Data 9 septembrie 2020 20:38:07
Problema Atac Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.84 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

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

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

int ancestor[NMAX][LOGNMAX + 2];
int length[NMAX][LOGNMAX + 2];
int level[NMAX];

void init( int n ) {
    int i, j;
    for ( i = 0; i < n; i ++ ) {
        for ( j = 0; j < LOGNMAX + 2; j ++ ) {
            ancestor[i][j] = -1;
            length[i][j] = -1;
        }
    }
}
void calculate_ancestors( int node, int lvl ) {
    level[node] = lvl;
    if ( node != 0 ) { /// != root
        int i;
        length[node][0] = father[node].value;
        ancestor[node][0] = father[node].children;
        i = 1;
        while ( ancestor[ancestor[node][i - 1]][i - 1] != -1 ) {
            ancestor[node][i] = ancestor[ancestor[node][i - 1]][i - 1];
            length[node][i] = min( length[node][i - 1], length[ancestor[node][i - 1]][i - 1] );
            i ++;
        }
    }
    for ( auto& x : edges[node] ) {
        calculate_ancestors( x.children, lvl + 1 );
    }
}
int same_level( int& node, int lvl ) {
    int minim, i;
    i = LOGNMAX + 1;
    minim = INF;
    while ( level[node] != lvl ) {
        while ( ancestor[node][i] == -1 || level[ancestor[node][i]] < lvl ) {
            i --;
        }
        minim = min( minim, length[node][i] );
        node = ancestor[node][i];
    }
    return minim;
}
int lca( int node1, int node2, int minim ) {
    int i, ok = 0;
    i = LOGNMAX + 1;
    while ( i >= 0 ) {
        while ( i >= 0 && ( ancestor[node1][i] == ancestor[node2][i] ) ) {
            i --;
        }
        if ( i == -1 ) {
            i = 0;
            ok = 1;
        }
        minim = min( min( minim, length[node1][i] ), length[node2][i] );
        node1 = ancestor[node1][i];
        node2 = ancestor[node2][i];
        i -= ok;
    }
    ///cout << endl;
    return minim;
}
int main() {
    ifstream fin( "atac.in" );
    ofstream fout( "atac.out" );
    int n, m, p, i, j, x, y, node, val, a, b, c, d, st, dr, minim;
    fin >> n >> m >> p;
    for ( i = 0; i < n - 1; i ++ ) {
        fin >> node >> val;
        edges[node - 1].push_back( { i + 1, val } );
        father[i + 1] = { node - 1, val };
    }

    init( n );
    calculate_ancestors( 0, 0 );
    fin >> x >> y >> a >> b >> c >> d;
    for ( i = 0; i < m; i ++ ) {
        st = x - 1;
        dr = y - 1;
        if ( level[dr] > level[st] )
            swap( st, dr );
        minim = same_level( st, level[dr] );
        minim = lca( st, dr, minim );
        if ( i >= m - p ) {
            fout << minim << '\n';
        }
        x = ( x * a + y * b ) % n + 1;
        y = ( y * c + minim * d ) % n + 1;
    }
    return 0;
}