Cod sursa(job #1934871)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 21 martie 2017 21:21:35
Problema Atac Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.89 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>


const int N = 32010;
const int LOGN = 16;
const int INF = 1e8 ;


using namespace std;

int noNodes, noQueries , noAnswers;

vector <pair < int , int > > edges [ N ];

int viz[ N ];
int height [ N ] ;
int anchestor[ N ][ LOGN ] , bestEdge [ N ][ LOGN ];


void ComputeMat( int node ){
    static int i ;

    for ( i = 1 ; ( 1<<i ) <= height [ node ] ; i++ ){
        anchestor [ node ][ i ] = anchestor [ anchestor [ node ][ i - 1 ] ][ i - 1 ] ;
        bestEdge [ node ][ i ] = min ( bestEdge [ node ][ i - 1 ] , bestEdge [ anchestor [ node ][ i - 1 ] ][ i - 1 ] ) ;
    }

}

void dfs ( int node  ){
    vector <pair < int , int > >::iterator it ;
    int  vec ;

    viz [ node ]  = 1 ;

    for ( it = edges[ node ].begin() ; it != edges[ node ].end() ; it++ ){
        vec = it->first ;

        if ( viz [ vec ] ){
            continue;
        }

        anchestor [ vec ] [ 0 ] = node ;
        bestEdge [ vec ] [ 0 ] = it->second ;
        height [ vec ] = height [ node ] + 1 ;

        ComputeMat( vec );

        dfs( vec );

    }

}

int SolveQuery( int x , int y ){
    static int diff , bestMuc ,i;

    if ( height [ x ] < height [ y ] ){
        int temp = x;
        x = y ;
        y = temp ;
    }
    bestMuc = INF ;
    diff = height [ x ]- height [ y ];
    for ( i = LOGN ; i >= 0 ; i -- )
        if ( ( 1<<i ) <= diff ){
            bestMuc = min ( bestMuc , bestEdge [ x ][ i ] );
            x = anchestor [ x ] [ i ] ;
            diff -= 1<<i ;
        }

    if ( x == y ){
        return bestMuc ;
    }

    for ( i = LOGN ; i>=0 ; i-- ){
        if ( anchestor [ x ] [ i ] == anchestor [ y ][ i ] || ( 1<<i ) >= height[ x ] ){
            continue;
        }
        bestMuc = min ( bestMuc , bestEdge[ x ] [ i ] );
        bestMuc = min ( bestMuc , bestEdge[ y ] [ i ] );

        x = anchestor [ x ][ i ] ;
        y = anchestor [ y ][ i ] ;

    }

    bestMuc = min( bestMuc , bestEdge [ x ][ 0 ] );
    bestMuc = min( bestMuc , bestEdge [ y ][ 0 ] );

    return bestMuc ;
}

int main(){
    int i ;

    freopen("atac.in","r",stdin);
    freopen("atac.out","w",stdout);

    scanf("%d%d%d",&noNodes, &noQueries , &noAnswers );

    int x , y , cost  ;
    for ( i = 2 ; i <= noNodes ; i ++ ){
        scanf("%d%d",&x , &cost);
        edges [ x ].push_back( make_pair( i ,cost ) );
        edges [ i ].push_back( make_pair( x ,cost ) );
    }

    dfs( 1 );

    int A , B , C , D , sol;

    scanf("%d%d%d%d%d%d",&x,&y,&A,&B,&C,&D);

    for ( i = 0 ; i < noQueries ; i++ ){

        sol = SolveQuery( x , y );

        if ( i >= noQueries - noAnswers ){
            printf("%d\n",sol);
        }
        x = ( x * A + y * B )% noNodes + 1;
        y = ( y * C + sol * D )% noNodes + 1;

    }

    return 0;
}