Cod sursa(job #1481353)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 4 septembrie 2015 11:40:03
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
#include<fstream>
#include<vector>

using namespace std;

ifstream fin( "atac.in" ); ofstream fout( "atac.out" );

const int nmax = 32000;
const int logmax = 15;
const int inf = 1 << 30;
int n, z;
int d[ logmax + 1 ][ nmax + 1 ];
int minval[ logmax + 1 ][ nmax + 1 ];
int h[ nmax + 1 ], tata[ nmax + 1 ];

struct muchie {
    int y, cost;

    muchie() {}
    muchie( int _y, int _cost ) : y( _y ), cost( _cost ) {}
};
vector< muchie > g[ nmax + 1 ];

void dfs( int nod ) {
    for( vector< muchie >::iterator it = g[ nod ].begin(); it != g[ nod ].end(); ++ it ) {
        if ( (it -> y) != tata[ nod ] ) {
            tata[ it -> y ] = nod;
            h[ it -> y ] = h[ nod ] + 1;
            minval[ 0 ][ it -> y ] = it -> cost;
            dfs( it -> y );
        }
    }
}
inline int min2( int a, int b ) {
    return ( a < b ? a : b );
}
void dinamicuta() {
    for( int i = 1; i <= n; ++ i ) {
        d[ 0 ][ i ] = tata[ i ];
    }

    for( int i = 1; (1 << i) <= n; ++ i ) {
        for( int j = 1; j <= n; ++ j ) {
            d[ i ][ j ] = d[ i - 1 ][ d[ i - 1 ][ j ] ];
            minval[ i ][ j ] = min2( minval[ i - 1 ][ j ], minval[ i - 1 ][ d[ i - 1 ][ j ] ] );
        }
    }
}
void urcare( int &nod, int dist ) {
    for( int i = 0; (1 << i) <= dist; ++ i ) {
        if ( dist & (1 << i) ) {
            z = min2( z, minval[ i ][ nod ] );
            nod = d[ i ][ nod ];
        }
    }
}
void solve( int x, int y ) {
    if ( x == y ) {
        z = 0; return ;
    }
    z = inf;
    if ( h[ x ] > h[ y ] ) {
        urcare( x, h[ x ] - h[ y ] );
    } else {
        urcare( y, h[ y ] - h[ x ] );
    }

    int n2;
    for( n2 = 1; (1 << n2) <= n; ++ n2 ) {
    }
    for( int step = n2; step >= 0; step -- ) {
        if ( d[ step ][ x ] != d[ step ][ y ] ) {
            z = min2( min2( z, minval[ step ][ x ] ), minval[ step ][ y ] );
            x = d[ step ][ x ];
            y = d[ step ][ y ];
        }
    }
    if ( x != y ) {
        z = min2( minval[ 0 ][ x ], minval[ 0 ][ y ] );
    }
}
int main() {
    int m, p;
    fin >> n >> m >> p;
    for( int i = 2; i <= n; ++ i ) {
        int x, y;
        fin >> x >> y;
        g[ i ].push_back( muchie( x, y ) );
        g[ x ].push_back( muchie( i, y ) );
    }

    dfs( 1 );
    dinamicuta();

    int x, y, a, b, c, d;
    fin >> x >> y >> a >> b >> c >> d;
    for( int i = 0; i < m; ++ i ) {
        solve( x, y );
        if ( m - p <= i ) {
            fout << z << "\n";
        }

        int xi, yi;
        xi = ( x * a + y * b ) % n + 1;
        yi = ( y * c + z * d ) % n + 1;
        x = xi;
        y = yi;
    }
    fin.close();
    fout.close();
    return 0;
}