Cod sursa(job #734585)

Utilizator Catah15Catalin Haidau Catah15 Data 14 aprilie 2012 16:35:03
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;


#define maxN 32010
#define maxK 16
#define inf (1 << 30)
#define PB push_back
#define MKP make_pair
#define f first
#define s second

int N, Level[maxN], Ap[maxN];
int Euler[maxN << 1], rmq[maxK << 1][maxN << 1];
int Father[maxK][maxN], MinE[maxK][maxN];
int Lg[maxK << 1];
vector <pair <int, int> > List[maxN];


void DFS (int nod)
{
    Euler[++ Euler[0]] = nod;
    Ap[nod] = Euler[0];

    for (int i = 0; i < List[nod].size(); ++ i)
    {
        int nod2 = List[nod][i].f, cost2 = List[nod][i].s;

        Level[nod2] = Level[nod] + 1;
        Father[0][nod2] = nod;
        MinE[0][nod2] = cost2;

        DFS (nod2);
        Euler[++ Euler[0]] = nod;
    }
}


void RMQ ()
{
    for (int i = 1; (1 << i) <= N; ++ i)
        for (int j = 1; j <= N; ++ j)
        {
            Father[i][j] = Father[i - 1][Father[i - 1][j]];
            MinE[i][j] = min (MinE[i - 1][MinE[i - 1][j]], MinE[i - 1][j]);
        }

    for (int i = 1; i <= Euler[0]; ++ i) rmq[0][i] = Euler[i];

    for (int i = 1; (1 << i) <= Euler[0]; ++ i)
        for (int j = 1; j <= Euler[0] - (1 << i) + 1; ++ j)
            if (Level[rmq[i - 1][j]] < Level[rmq[i - 1][j + (1 << (i - 1))]]) rmq[i][j] = rmq[i - 1][j];
            else rmq[i][j] = rmq[i - 1][j + (1 << (i - 1))];
}


inline int LCA (int X, int Y)
{
    if (X > Y) swap (X, Y);

    int nrE = Y - X + 1;
    int K = Lg[nrE];

    if (Level[rmq[K][X]] < Level[rmq[K][Y - (1 << K) + 1]]) return rmq[K][X];
    else return rmq[K][Y - (1 << K) + 1];
}


inline int Get_MinE (int X, int Y)
{
    if (X == Y) return inf;

    int K = Lg[Level[X] - Level[Y]];
    return min (MinE[K][X], Get_MinE(Father[K][X], Y));
}


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

    int M, P;
    scanf ("%d %d %d", &N, &M, &P);

    for (int i = 2, U, V; i <= N; ++ i)
    {
        scanf ("%d %d", &U, &V);
        List[U].PB (MKP (i, V));
    }

    DFS (1);
    RMQ ();

    for (int i = 2; i <= Euler[0]; ++ i) Lg[i] = Lg[i / 2] + 1;

    int X, Y, A, B, C, D;
    scanf ("%d %d %d %d %d %d", &X, &Y, &A, &B, &C, &D);

    for (int i = 1; i <= M; ++ i)
    {
        int Z = LCA (Ap[X], Ap[Y]);
        int ans = min (Get_MinE (X, Z), Get_MinE (Y, Z));

        if (ans == inf) ans = 0;
        if (i > M - P) printf ("%d\n", ans);

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

    return 0;
}