Cod sursa(job #2323540)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 19 ianuarie 2019 12:14:26
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.79 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 lca_fun ( int i , int j )
{
    int st = firstap [ i ] , dr = firstap [ j ] ;
    if ( dr < st )  swap ( dr , st ) ;
    int log = lg [ dr - st + 1 ] ;
    if ( level [ rmq [ log ][ st ] ] < level [ rmq [ log ][ dr - ( 1 << log ) + 1 ] ] )
        return rmq [ log ][ st ] ;
    return rmq [ log ][ dr - ( 1 << log ) + 1 ] ;
}
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 = lca_fun( 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() ;
}