Cod sursa(job #654616)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 30 decembrie 2011 18:12:23
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <cstdio>
#include <vector>
#include <algorithm>

#define NMax 32005
#define LogMax 16
#define Infinity 2000000000
#define v first
#define c second

using namespace std;

vector < pair <int, int> > G[NMax];
int N, Level[NMax], F[LogMax][NMax], Min[LogMax][NMax], Log2[NMax];
int A, B, C, D, M, P;

inline void BuildLog2 ()
{
    for (int i=2; i<=N; ++i)
    {
        Log2[i]=Log2[i/2]+1;
    }
}

inline int LCA (int X, int Y)
{
    for (; Level[X]<Level[Y]; Y=F[Log2[Level[Y]-Level[X]]][Y]);
    for (; Level[Y]<Level[X]; X=F[Log2[Level[X]-Level[Y]]][X]);
    if (X==Y)
    {
        return X;
    }
    for (int Step=Log2[Level[X]]; Step>=0; --Step)
    {
        if (F[Step][X]!=F[Step][Y])
        {
            X=F[Step][X];
            Y=F[Step][Y];
        }
    }
    return F[0][X];
}

inline int FindMin (int X, int K)
{
    int CMin=Infinity;
    for (; K>0; CMin=min (CMin, Min[Log2[K]][X]), X=F[Log2[K]][X], K-=(1<<Log2[K]));
    return CMin;
}

inline int Query (int X, int Y)
{
    if (X==Y)
    {
        return 0;
    }
    int Z=LCA (X, Y);
    return min (FindMin (X, Level[X]-Level[Z]), FindMin (Y, Level[Y]-Level[Z]));
}

inline void BuildRMQ ()
{
    for (int K=1; K<=Log2[N]; ++K)
    {
        for (int X=1; X<=N; ++X)
        {
            F[K][X]=F[K-1][F[K-1][X]];
            Min[K][X]=min (Min[K-1][X], Min[K-1][F[K-1][X]]);
        }
    }
}

inline void DFS (int X)
{
    for (unsigned i=0; i<G[X].size (); ++i)
    {
        int V=G[X][i].v;
        int C=G[X][i].c;
        if (V!=F[0][X])
        {
            F[0][V]=X;
            Min[0][V]=C;
            Level[V]=Level[X]+1;
            DFS (V);
        }
    }
}

int main()
{
    freopen ("atac.in", "r", stdin);
    freopen ("atac.out", "w", stdout);
    scanf ("%d %d %d", &N, &M, &P);
    for (int i=2; i<=N; ++i)
    {
        int X, Y;
        scanf ("%d %d", &X, &Y);
        G[X].push_back (make_pair (i, Y));
        G[i].push_back (make_pair (X, Y));
    }
    BuildLog2 ();
    DFS (1);
    BuildRMQ ();
    int X, Y, Z;
    scanf ("%d %d %d %d %d %d", &X, &Y, &A, &B, &C, &D);
    for (; M>0; --M)
    {
        Z=Query (X, Y);
        X=(X*A+Y*B)%N+1;
        Y=(Y*C+Z*D)%N+1;
        if (M<=P)
        {
            printf ("%d\n", Z);
        }
    }
    return 0;
}