Cod sursa(job #952686)

Utilizator primulDarie Sergiu primul Data 23 mai 2013 20:03:07
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.18 kb
#include <iostream>
#include <fstream>
#include <vector>
 
using namespace std;
 
ifstream in ("atac.in");
ofstream out ("atac.out");
 
const int MAXN = 32010 * 2;
 
int N;
vector <int> Graf[MAXN];
int H[MAXN * 2], First[MAXN * 2], Lvl[MAXN * 2], Niv[MAXN * 2];
int RMQ[17][MAXN], V[MAXN], Seq[MAXN * 2];
int Log[MAXN];
int T[17][MAXN], DP[17][MAXN], Father[MAXN];
int now, now2;
 
void DFS (int nod, int lev)
{
    ++ now;
    H[now] = nod;
    Lvl[now] = lev;
    Niv[nod] = 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 (i = 1; i <= now; i ++)
        RMQ[0][i] = i;
 
    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_Stramosi ()
{
    int i, j;
 
    for (i = 2; i <= N; i ++)
        T[0][i] = Father[i], DP[0][i] = V[i];
 
    for (i = 1; (1 << i) <= N; i ++)
        for (j = 1; j <= N; j ++){
            if ((1 << i) >= Niv[j])
                continue;
 
            T[i][j] = T[i - 1][T[i - 1][j]];
            DP[i][j] = DP[i - 1][j];
 
            if (DP[i - 1][T[i - 1][j]] < DP[i][j])
                DP[i][j] = DP[i - 1][T[i - 1][j]];
        }
}
 
int Query (int X, int Y)
{
    int i, dif = Niv[X] - Niv[Y], Ans = (1 << 30);
 
    for (i = 0; (1 << i) <= dif; i ++)
        if (dif & (1 << i)){
            if (DP[i][X] < Ans)
                Ans = DP[i][X];
 
            X = T[i][X];
        }
 
    return Ans;
}
 
int Solve (int X, int Y)
{
    if (X == Y)
        return 0;
 
    int lca, a, b;
    lca = H[LCA (X, Y)];
 
    a = Query (X, lca);
    b = Query (Y, lca);
 
    return min (a, b);
}
 
int main()
{
    int M, P, i, a, X, Y, Z, A, B, C, D, newX, newY;
 
    in >> N >> M >> P;
 
    for (i = 2; i <= N; i ++){
        in >> Father[i] >> V[i];
 
        Graf[Father[i]].push_back (i);
    }
    V[1] = (1 << 30);
    in >> X >> Y >> A >> B >> C >> D;
 
    DFS (1, 1);
    Build_Log ();
    Build_RMQ ();
    Build_Stramosi ();
 
    for (i = 1; i <= M; i ++)
    {
        Z = Solve (X, Y);
 
        if (i >= M - P + 1)
            out << Z << "\n";
 
        newX = (X * A + Y * B) % N + 1;
        newY = (Y * C + Z * D) % N + 1;
        X = newX;
        Y = newY;
    }
 
    return 0;
}