Cod sursa(job #2324201)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 20 ianuarie 2019 13:28:10
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.11 kb
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define sz size()
using namespace std;
const int NR = 32001 ;
const int oo = ( 1 << 30 ) ;
ifstream f ("atac.in") ;
ofstream g ("atac.out") ;
vector < pair < int , int > > v [ NR ] ;
int cnt , level [ NR ] , euler [ 2 * NR ] , rmq [ 20 ][ 2 * NR ] , rmq_father [ 16 ][ NR ] , rmq_edge [ 16 ][ NR ] , Father [ NR ] , Father_edge [ NR ] , firstap [ 2 * NR ] , lg [ 2 * NR ] , X , Y , Z , A , B , C , D , m , n , p ;
void input ()
{
    f >> n >> m >> p ;
    for ( int i = 2 ; i <= n ; ++ i )
    {
        int father = i , son , cost ;
        f >> son >> cost ;
        if ( father > son ) swap ( father , son ) ;
        v[ father ].pb ( mp ( son , cost ) ) ;
        v [ son ].pb ( mp ( father , cost ) ) ;
    }
    f >> X >> Y >> A >> B >> C >> D ;
}
void dfs ( int nod , int father , int cost )
{
    level [ nod ] = level [ euler [ cnt ] ] + 1 ;
    Father [ nod ] = father ;
     Father_edge [ nod ] = cost ;
    euler [ ++ cnt ] = nod ;
    firstap [ nod ] = cnt ;
    for ( size_t i = 0 ; i < v[  nod ].sz ; ++ i )
    {
        if ( !firstap [ v [ nod ][ i ].first ] )
        {
        dfs ( v [ nod ][ i ].first , nod , v [ nod ][ i ].second ) ;
        euler [ ++ cnt ] = nod ;
        }
    }
}
void rmq_fun (  )
{
    for ( int i = 2 ; i <= cnt ; ++ i ) lg [ i ] = lg [ i >> 1 ] + 1 ;
    for ( int i = 1 ; i <= cnt ; ++ i ) rmq [ 0 ][ i ] = euler [ i ] ;
    for ( int i = 1 ; ( 1 << i ) <= cnt ; ++ i )
    for ( int j = 1 ; j + ( 1 << i ) - 1 <= cnt ; ++ j )
    {
    rmq [ i ][ j ] = rmq [ i - 1 ][ j ] ;
    if ( level [ rmq [ i - 1 ] [ j ] ] > level [ rmq [ i - 1 ][ j + ( 1 << ( i - 1 ) ) ] ] )
    rmq [ i ][ j ] = rmq [ i - 1 ][ j + ( 1 << ( i - 1 ) ) ] ;
    }
}
int query ( int x , int y )
{
    int log , i ;
    if ( level [ x ] > level [ y ] )    swap ( x , y ) ;

    for ( log = 0 ; ( 1 << log ) <= level [ y ] ; log ++ ) ;


    while ( log -- )
    {
        if ( level [ y ] - ( 1 << log ) >= level [ x ] )    // practic ia fiecare bit al distantei
        y = rmq_father [ log ][ y ] ;                       //  level [ x ] - level [ y ] + 1
    }

    if ( x == y )   return x ;

    for (  i = 0 ; ( 1 << i ) < n ; ++ i )
    if ( rmq_father [ i ][ x ] != rmq_father [ i ][ y ] )
    {
        x = rmq_father [ i ][ x ] ;
        y = rmq_father [ i ][ y ] ;
    }

    return Father [ x ] ;

}

int rmq_father__rmq_edge_fun (  )
{
    int i , j ;
    for ( i = 1 ; i <= n ; ++ i )
    {
        rmq_father [ 0 ][ i ] = Father [ i ] ;
        rmq_edge [ 0 ][ i ] = Father_edge [ i ] ;
    }
    //rmq_edge [ i ][ j ] - muchia de cost minim dintre nodul j
    // si al 2 ^ i stramos al nodului j
    for ( i = 1 ; ( 1 << i ) <= n ; ++ i )
    for ( j = 1 ; j <= n ; ++ j )
    {
        rmq_father [ i ][ j ] = rmq_father [ i - 1 ][ rmq_father [ i - 1 ][ j ] ] ;
        rmq_edge [ i ][ j ] = min ( rmq_edge [ i - 1 ][ j ] , rmq_edge [ i - 1 ][ rmq_father [ i - 1 ][ j ] ] ) ;
    }
}
int min_edge ( int nod , int lca )
{
    if ( lca == nod )   return oo ;
    int log = lg [ level [ nod ] - level [ lca ] ] + 1 ;
    int nr = level [ nod ] - level [ lca ] ;
     int min_edge = ( 1 << 30 ) ;
        while ( log --  )
        if ( ( ( 1 << log ) & nr )  )
        {
        min_edge = min ( rmq_edge [ log ][ nod ] , min_edge ) ;
        nod = rmq_father [ log ][ nod ] ;
        // pe masura ce urcam 2 ^ log nivele actualizam si min_edge cu
        //valoarea muchiei de cost minim de pe lant , daca e cazul
        }
        return min_edge ;
}
int task ( int x , int y )
{
    int lca = query( x , y ) ;
    return min ( min_edge( x , lca ) , min_edge( y , lca ) ) ;
}
void solve()
{
    for ( int i = 1 ; i <= m ; ++ i )
    {
        if ( X == Y )   Z = 0 ;
        else            Z = task( X , Y ) ;
        if ( i >= m - p + 1 )   g << Z << "\n" ;
        X = ( X * A + Y * B ) % n + 1 ;
        Y = ( Y * C + Z * D ) % n + 1 ;
    }
}
int main ()
{
    input() ;
    dfs( 1, 0 , 1 << 30  ) ;
    rmq_fun() ;
    rmq_father__rmq_edge_fun() ;
    solve() ;
}