Cod sursa(job #1669852)

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

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

struct str{ int node, cost; }; bitset <(1 << DIM)> Marked;
int Father[1 << DIM][DIM], Level[1 << DIM], Best[1 << DIM][DIM], X, Y, Z, V1, V2, V3;
vector <str> Edge[1 << DIM]; int nr_nodes, nr_querys, nr_answers, node, cost, V4;

void DFS( int node, int level, int minim ) {
    Level[node] = level; Best[node][0] = minim; Marked[node] = 1;

    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 <str> :: iterator it;
    for( it = Edge[node].begin(); it != Edge[node].end(); it ++ ) {
        str next_node = *it;

        if( !Marked[next_node.node] )
            DFS( next_node.node, level + 1, next_node.cost );
    }

    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, cost} );
    }

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

    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;
}