Cod sursa(job #945247)

Utilizator Stefex09Stefan Teodorescu Stefex09 Data 1 mai 2013 15:07:03
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.1 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream in ("atac.in");
ofstream out ("atac.out");

const int MAXN = 32010 * 2;

vector <int> Graf[MAXN];
int H[MAXN * 2], First[MAXN * 2], Lvl[MAXN * 2];
int RMQ[17][MAXN], V[MAXN], Seq[MAXN * 2];
int Log[MAXN], AINT[1 << 17];
int now, now2;

void DFS (int nod, int lev)
{
    ++ now;
    H[now] = nod;
    Lvl[now] = lev;
    First[nod] = now;
    Seq[++ now2] = V[nod];

    for (auto it = Graf[nod].begin (); it != Graf[nod].end (); ++ it){
        DFS (*it, lev + 1);

        ++ now;
        H[now] = nod;
        Lvl[now] = lev;
    }

    Seq[++ now2] = V[nod];
}

void Build_Log ()
{
    int i;

    for (i = 2; i < MAXN; i ++)
        Log[i] = Log[i / 2] + 1;
}

void Build_RMQ ()
{
    int i, j, a, b;

    for (j = 1; (1 << j) <= now; j ++)
        for (i = 1; i + (1 << j) <= now; i ++){
            a = RMQ[j - 1][i];
            b = RMQ[j - 1][i + (1 << (j - 1))];

            if (Lvl[a] <= Lvl[b])
                RMQ[j][i] = a;
            else
                RMQ[j][i] = b;
        }
}

int LCA (int nod1, int nod2)
{
    nod1 = First[nod1];
    nod2 = First[nod2];

    if (nod2 < nod1)
        swap (nod1, nod2);

    int dif = nod2 - nod1 + 1;
    int log = Log[dif];
    int a, b;
    a = RMQ[log][nod1];
    b = RMQ[log][nod2 - (1 << log) + 1];

    if (Lvl[a] <= Lvl[b])
        return a;
    else
        return b;
}

void Build_AINT (int nod, int st, int dr)
{
    if (st == dr){
        AINT[nod] = Seq[st];
        return;
    }

    int mid = (st + dr) / 2;

    Build_AINT (nod * 2, st, mid);
    Build_AINT (nod * 2 + 1, mid + 1, dr);

    AINT[nod] = min (AINT[nod * 2], AINT[nod * 2 + 1]);
}

int query (int nod, int st, int dr, int a, int b)
{
    if (a <= st && dr <= b)
        return AINT[nod];

    int mid = (st + dr) / 2;
    int aux1 = (1 << 30), aux2 = (1 << 30);

    if (a <= mid)
        aux1 = query (nod * 2, st, mid, a, b);
    if (mid < b)
        aux2 = query (nod * 2 + 1, mid + 1, dr, a, b);

    return min (aux1, aux2);
}

int Solve (int X, int Y)
{
    if (X == Y)
        return 0;

    int lca, a, b;
    lca = H[LCA (X, Y)];

    a = query (1, 1, now2, First[lca], First[X]);
    b = query (1, 1, now2, First[lca], First[Y]);

    return min (a, b);
}

int main()
{
    int N, M, P, i, a, b, c, X, Y, Z, A, B, C, D;

    in >> N >> M >> P;

    for (i = 2; i <= N; i ++){
        in >> a >> b;

        Graf[a].push_back (i);
        V[i] = b;
    }
    V[1] = (1 << 30);
    in >> X >> Y >> A >> B >> C >> D;

    DFS (1, 1);
    Build_Log ();
    Build_RMQ ();
    Build_AINT (1, 1, now2);

    if (P < M){
        for (i = 1; i <= M - P + 1; i ++){
            Z = Solve (X, Y);

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

    for (i -- ; i <= M; i ++){
        Z = Solve (X, Y);

        out << Z << "\n";

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

    return 0;
}