Cod sursa(job #1669850)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 31 martie 2016 10:00:03
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <bits/stdc++.h>

const int DIM = 15;
const int INF = 0x3f3f3f3f;
using namespace std;

int Father[1 << DIM][DIM], Level[1 << DIM], Best[1 << DIM][DIM], X, Y, Z, V1, V2, V3;
vector <int> Edge[1 << DIM]; int nr_nodes, nr_querys, nr_answers, node, cost, V4;

void DFS( int node, int level ) {
    Level[node] = level;

    for( int k = 1; k < DIM; k ++ ) {
        Father[node][k] = Father[ Father[node][k - 1] ][k - 1];
        Best[node][k] = min( Best[node][k - 1], Best[ Father[node][k - 1] ][k - 1] );
    }

    vector <int> :: iterator it;
    for( it = Edge[node].begin(); it != Edge[node].end(); it ++ ) {
        int next_node = *it;

        DFS( next_node, level + 1 );
    }

    return;
}

int get_minim( int X, int Y ) {
    int minim = INF;

    if( Level[X] > Level[Y] )
        swap( X, Y );

    for( int k = 14; k >= 0; k -- ) {
        if( Level[Y] - (1 << k) < Level[X] )
            continue;

        minim = min( minim, Best[Y][k] );
        Y = Father[Y][k];
    }

    for( int k = 14; k >= 0; k -- ) {
        if( Father[X][k] == Father[Y][k] )
            continue;

        minim = min( minim, min( Best[X][k], Best[Y][k] ) );
        X = Father[X][k]; Y = Father[Y][k];
    }

    if( X != Y )
        minim = min( minim, min( Best[X][0], Best[Y][0] ) );
    else
        minim = 0;

    return minim;
}

int main() {

    FILE *input_file  = fopen( "atac.in" , "r" );
    FILE *output_file = fopen( "atac.out", "w" );

    fscanf( input_file, "%d %d %d", &nr_nodes, &nr_querys, &nr_answers );

    for( int i = 2; i <= nr_nodes; i ++ ) {
        fscanf( input_file, "%d %d", &node, &cost );

        Father[i][0] = node; Best[i][0] = cost;
        Edge[node].push_back(i);
    }

    memset( Best[0], INF, sizeof(Best[0]) );
    Best[1][0] = INF; DFS( 1, 1 );

    fscanf( input_file, "%d %d %d %d %d %d", &X, &Y, &V1, &V2, &V3, &V4 );

    for( int i = 1; i <= nr_querys; i ++ ) {
        Z = get_minim( X, Y );

        if( i >= nr_querys - nr_answers + 1 )
            fprintf( output_file, "%d\n", Z );

        X = ( X * V1 + Y * V2 ) % nr_nodes + 1;
        Y = ( Y * V3 + Z * V4 ) % nr_nodes + 1;
    }

    return 0;
}