Cod sursa(job #2098651)

Utilizator robx12lnLinca Robert robx12ln Data 3 ianuarie 2018 12:53:31
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include<fstream>
#include<algorithm>
#include<deque>
#include<cstring>
#include<vector>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
int N, M, P, Lca[32005][16], Rmq[32005][16], LOG;
int X, Y, A, B, C, D, Z, X1, Y1;
int Niv[32005], f[32005];
vector< pair<int,int> > v[32005];
deque<int> Ans;
void dfs( int nod, int nr ){
    f[nod] = 1;
    Niv[nod] = nr;
    for( int i = 0; i < v[nod].size(); i++ ){
        int vecin = v[nod][i].first;
        if( f[vecin] == 0 ){
            Lca[vecin][0] = nod;
            Rmq[vecin][0] = v[nod][i].second;
            dfs( vecin, nr + 1 );
        }
    }
    return;
}
inline int LCA( int a, int b ){
    if( Niv[a] > Niv[b] )
        swap( a, b );
    int D = Niv[b] - Niv[a];
    int x = 0;
    while( D != 0 ){
        if( ( D & 1 ) == 1 )
            b = Lca[b][x];
        x++;
        D >>= 1;
    }
    for( int i = LOG; i >= 0; i-- ){
        if( Lca[a][i] != Lca[b][i] ){
            a = Lca[a][i];
            b = Lca[b][i];
        }
    }
    if( a == b )
        return a;
    else
        return Lca[a][0];
}
inline int solve1( int nod, int D ){
    int r = 0x3f3f3f3f;
    int x = 0;
    while( D != 0 ){
        if( ( D & 1 ) == 1 ){
            r = min( r, Rmq[nod][x] );
            nod = Lca[nod][x];
        }
        x++;
        D >>= 1;
    }
    return r;
}
inline int solve( int X, int Y ){
    if( X == Y )
        return 0;
    int nod = LCA( X, Y );
    return min( solve1( X, Niv[X] - Niv[nod] ), solve1( Y, Niv[Y] - Niv[nod] ) );
}
int main(){
    fin >> N >> M >> P;
    for( int i = 1; i < N; i++ ){
        int a, b;
        fin >> a >> b;
        v[i + 1].push_back( make_pair( a, b ) );
        v[a].push_back( make_pair( i + 1, b ) );
    }
    memset( Rmq, 0x3f3f3f3f, sizeof(Rmq) );
    dfs( 1, 1 );
    for( int k = 1; (1<<k) <= N; k++, LOG = k )
        for( int i = 1; i <= N; i++ )
            Lca[i][k] = Lca[ Lca[i][k - 1] ][k - 1];
    for( int k = 1; (1<<k) <= N; k++ )
        for( int i = 1; i <= N; i++ )
            Rmq[i][k] = min( Rmq[i][k - 1], Rmq[ Lca[i][k - 1] ][k - 1] );
    fin >> X >> Y >> A >> B >> C >> D;
    for( int i = 1; i <= M; i++ ){
        Z = solve( X, Y );
        Ans.push_back( Z );
        if( Ans.size() == P + 1 )
            Ans.pop_front();
        X1 = ( X * A + Y * B ) % N + 1;
        Y1 = ( Y * C + Z * D ) % N + 1;
        X = X1;
        Y = Y1;
    }
    for( int i = 0; i < Ans.size(); i++ )
        fout << Ans[i] << "\n";
    return 0;
}