Cod sursa(job #2313531)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 7 ianuarie 2019 00:19:39
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.49 kb
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define sz size()
using namespace std;
const int NR = 32001 ;
ifstream f("atac.in");
ofstream g("atac.out");
int level [ NR ] ;                  // hai ca nu-i greu
int euler [ NR * 2 ] ;             // parcurgerea euler
int rmq [ 18 ][ 2 * NR ] ;         //   rmq [ i ][ j ] - nodul de nivel minim din lantul [ i - j ]
int firstap [ NR * 2 ] ;           //   prima aparitie in euler
int lg [ NR * 2 ] ;                 // ??
int cnt , n , m , p , Z , X , Y , A , B , C , D ;
int TT [ NR ] ;                     // TT [ i ] - tatal lui i
int TTC [ NR ] ;                    // TTC [ i ] - costul muchiei [ i - TT [ i ] ]
int rmq_stramosi [ 16 ][ NR ] ; // rmq_stramosi [ i ][ j ] - costul minim al unei muchii din lantul [ j - al ( 2 ^ i - lea parinte al lui j ) ]
// rmqTT [ i ][ j ]                     - al 2 ^ i - lea strabun al lui j

vector < pair < int , int > > v [ NR ] ;    // V [ i ] - retine fii nodului i
void intput ()
{
    f >> n >> m >> p;
    for ( int i = 2 ; i <= n ; ++ i )
    {
        int son , father = i , cost ;
        f >> son >> cost ;
        if ( son < father ) swap ( son , father ) ;
        v [ father ].pb ( mp ( son , cost ) ) ;
        TT [ son ] = father ;
        TTC [ son ] = cost ;
    }
    f >> X >> Y >> A >> B >> C >> D ;
}
int dfs ( int nod )
{
    euler [ ++ cnt ] = nod ;
    firstap [ nod ] = cnt ;
    for ( size_t i = 0 ; i < v [ nod ].sz ; ++ i )
    {
        int vecin = v [ nod ][ i ].first ;
        int cost =  v [ nod ][ i ].second ;
        level [ vecin ] = level [ nod ] + 1 ;
        dfs ( vecin ) ;
        euler [ ++ cnt ] = nod ;
    }
}
void rmmq ()
{
    for ( int i = 1 ; i <= cnt ; ++ i )  rmq [ 0 ][ i ] = euler [ i ] ;
    for ( int i = 2 ; i <= cnt ; ++ i ) lg [ i ] = lg [ i >> 1 ] + 1 ;

    for ( int i = 1 ; i <= lg [ cnt ] ; ++ i )
    for ( int j = 1 ; j + ( 1 << i ) <= cnt + 1 ; ++ j )
    {
        if ( level [ rmq [ i - 1 ][ j ] ] < level [ rmq [ i - 1 ][ j + ( 1 << ( i - 1 ) ) ] ] )
            rmq [ i ][ j ] = rmq [ i - 1 ][ j ] ;
        else
            rmq [ i ][ j ] = rmq [ i - 1 ][ j + ( 1 << ( i - 1 ) ) ] ;
    }
}
void idem_stramosi()
{
    int rmqTT [ 16 ][ NR ] = { 0 } ;
     for ( int j = 1 ; j <= n ; j ++ )  rmqTT [ 0 ][ j ] = TT [ j ] ;

    for ( int  i = 1  ; ( 1 << i ) <= n ; ++ i )
    for ( int j = 1 ; j <= n ; j ++ )
    rmqTT [ i ][ j ] = rmqTT [ i - 1 ][ rmqTT [ i - 1 ][ j ] ] ;

    for (int i = 1 ; i <= n ; ++ i )    rmq_stramosi [ 0 ][ i ] = TTC [ i ] ;
    for ( int i = 1 ; ( 1 << i ) <= n ; ++ i )
    for ( int j = 1 ; j <= n ; ++ j )
    {
        rmq_stramosi [ i ][ j ] = rmq_stramosi [ i - 1 ][ j ] ;
        if ( rmq_stramosi [ i - 1 ][ rmqTT [ i - 1 ][ j ]  ] < rmq_stramosi [ i ][ j ] && rmq_stramosi [ i - 1 ][ rmqTT [ i - 1 ][ j ] ] > 0 )
        rmq_stramosi [ i ][ j ] = rmq_stramosi [ i - 1 ][ rmqTT [ i - 1 ][ j ]  ] ;
    }
}
int task ( int x , int y )
{
    int st = firstap [ x ] , minim =  ( 1 << 30 ) , dr = firstap [ y ] , lca , dist;
    if ( dr < st )    swap ( dr , st ) ;
    dist = dr - st + 1 ;
    if ( level [ rmq  [ lg [ dist ] ][ st ] ] < level [ rmq [ lg [ dist ] ][ dr - ( 1 << ( lg [ dist ]  ) ) + 1 ] ] )
        lca = rmq  [ lg [ dist ] ][ st ]  ;
    else
        lca = rmq [ lg [ dist ] ][ dr - ( 1 << ( lg [ dist ]  ) ) + 1  ] ;
    dist = lg [ level [ x ] - level [ lca ] + 1 ] + 1 ;
    if   ( rmq_stramosi [ dist ][ x ] && rmq_stramosi [ dist ][ x ] < minim ) minim = rmq_stramosi [ dist ][ x ] ;
    if   ( rmq_stramosi [ dist ][ x - ( 1 <<  dist  ) + 1 ] &&  rmq_stramosi [ dist ][ x - (1 << dist ) + 1 ] < minim ) minim = rmq_stramosi [ dist ][ x - ( 1 << dist  ) + 1 ] ;
    dist = lg [ level [ y ] - level [ lca ] + 1 ] + 1 ;
    if  ( rmq_stramosi [ dist ][ x ] && rmq_stramosi [ dist ][ x ] < minim ) minim = rmq_stramosi [ dist ][ x ] ;
    if   ( rmq_stramosi [ dist ][ x - ( 1 <<  dist  ) + 1 ] &&  rmq_stramosi [ dist ][ x - (1 << dist ) + 1 ] < minim ) minim = rmq_stramosi [ dist ][ x - ( 1 << dist  ) + 1 ] ;
     return minim ;
}
int solve_tasks ()
{
    for ( int i = 1 ; i <= m ; ++ i )
    {
        if ( X != Y )   Z = task ( X , Y ) ;
        else            Z = 0 ;
        if ( i >= p )   g << Z << "\n" ;
        X = ( X * A + Y * B ) % n + 1 ;
        Y = ( Y * C + Z * D ) % n + 1 ;
    }
}

int main ()
{
intput() ;
dfs( 1 ) ;
rmmq() ;
idem_stramosi() ;
solve_tasks() ;
f.close() ;
g.close() ;
return 0 ;

}