Cod sursa(job #2311342)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 2 ianuarie 2019 22:43:26
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#define sz size()
#define pb push_back
using namespace std ;
ifstream f ("atac.in") ;
ofstream g ("atac.out") ;
const int NR = 32001 ;
vector < pair < int , int > > v [ NR ] ;
int firstap [ NR ] ,  euler_edges [ 2 * NR ] , X , Y , A , B , C , D , Z , cnt , n , m , q , a [ 2 * NR ][ 15 ] , lg [ 2 * NR ] ;
bool viz [ NR ] ;
void input (){
    f >> n >> m >> q ;
    for ( int i = 2 ; i <= n ; ++ i ){
        int x , y ; f >> x >> y ;
        v [ i ].pb( make_pair( x , y ) ) ;
        v [ x ].pb( make_pair( i , y ) ) ;}
    f >> X >> Y >> A >> B >> C >> D ;
    firstap [ 1 ] = 1 ;}
void euler_dfs ( int nod , int cost , int father ){
    viz [ nod ] = true ;
        for( size_t i = 0 ; i < v [ nod ].sz ; ++ i ){
            if ( !viz [ v [ nod ][ i ].first ] )
            {
            ++ cnt ;
            firstap [ v [ nod ][ i ].first ] = cnt + 1  ;
            euler_edges [ cnt ] = v [ nod ][ i ].second ;
            euler_dfs ( v [ nod ][ i ].first , v [ nod ][ i ].second , nod ) ;
            }}
        euler_edges [ ++ cnt ] = cost ;}
void rmq (){
cnt -- ;
int i , j ;
a [ 1 ][ 0 ] = euler_edges [ 1 ] ;
for ( i = 2 ; i <= cnt ; ++ i ) a [ i ][ 0 ] = euler_edges [ i ] , lg [ i ] = lg [ i >> 1 ] + 1 ;
for ( j = 1 ; j <= lg [ cnt ] ; ++ j )
for ( i = 1 ; i + ( 1 << j ) <= cnt + 1 ; ++ i )
a [ i ][ j ] = min ( a [ i ][ j - 1 ] , a [ i + ( 1 << ( j - 1 ) ) ][ j - 1 ] ) ;}
void solve_tasks (){
    for ( int i = 1 ; i <= m ; ++ i ){
        if ( X == Y )   Z = 0 ;
    else
        {int st = firstap [ X ] ;
        int dr = firstap [ Y ] - 1 ;
        if ( dr < st )  swap ( dr , st ) ;
        int interval = lg [ dr - st + 1 ] ;
        Z = min ( a [ st ][ interval ] , a [ dr + 1 - ( 1 << interval ) ][ interval ] ) ;}
        if ( i >= q )   g << Z << "\n" ;
        X = ( X * A + Y * B ) % n + 1 ;
        Y = ( Y * C + Z * D ) % n + 1 ;}}
int main (){
    input() ;
    euler_dfs( 1 , 0 , 0 ) ;
    rmq() ;
    solve_tasks() ;
    return 0 ;}