Cod sursa(job #1211015)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 21 iulie 2014 21:00:16
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 32e3 + 1;
const int Mmax = 5e5 + 1;
const int LgMax = 15 + 1;

vector < pair<int,int> > G[Nmax];
int rmq[LgMax][Nmax];
int father[Nmax], level[Nmax];

int N, M, P;
int X, Y, Z;
int A, B, C, D;

void DFS( int node )
{
    for ( auto x: G[node] )
    {
        if ( father[x.first] == 0 )
        {
            father[x.first] = node;
            rmq[0][x.first] = x.second;
            level[x.first] = level[node] + 1;

            DFS( x.first );
        }
    }
}

void build_rmq()
{
    for ( int i = 1; ( 1 << i ) <= N; ++i )
        for ( int j = 1; j + ( 1 << i ) - 1 <= N; ++j )
        {
            int p = 1 << ( i - 1 );

            rmq[i][j] = min( rmq[i - 1][j], rmq[i - 1][j + p] );
        }
}

int lca( int x, int y )
{
    while ( x != y )
    {
        if ( level[x] < level[y] )
            y = father[y];
        else
            x = father[x];
    }

    return x;
}

int get_min( int x, int y )
{
    int lg = LgMax - 1;

    if ( level[x] < level[y] )
        swap( x, y );

    if ( x == y )
        return 0;

    int L = lca( x, y );

    int sol = 1e9;

    while ( x != L )
    {
        sol = min( sol, rmq[0][x] );
        x = father[x];
    }

    while ( y != L )
    {
        sol = min( sol, rmq[0][y] );
        y = father[y];
    }

    return sol;
}

int main()
{
    ifstream in("atac.in");
    ofstream out("atac.out");

    in.sync_with_stdio( false );

    in >> N >> M >> P;

    for ( int i = 2, a, c; i <= N; ++i )
    {
        in >> a >> c;

        G[a].push_back( make_pair( i, c ) );
        G[i].push_back( make_pair( a, c ) );
    }

    in >> X >> Y >> A >> B >> C >> D;

    father[1] = 1;
    DFS( 1 );
    build_rmq();

    for ( int i = 1; i <= M; ++i )
    {
        Z = get_min( X, Y );

        if ( i >= P )
            out << Z << "\n";

        X = ( X * A + Y * B ) % N + 1;
        Y = ( Y * C + Z * D ) % N + 1;
    }

    return 0;
}