Cod sursa(job #997864)

Utilizator poptibiPop Tiberiu poptibi Data 14 septembrie 2013 23:42:25
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int NMAX = 32005, INF = 0x3f3f3f3f;

int N, M, P, X, Y, V, A, B, C, D, Anc[16][NMAX], Min[16][NMAX], Level[NMAX];
vector<pair<int, int> > G[NMAX];
bool Used[NMAX];

void DFS(int Node, int Father, int B, int L)
{
    Anc[0][Node] = Father;
    Min[0][Node] = B;
    Level[Node] = L;
    Used[Node] = 1;

    for(vector<pair<int, int> > :: iterator it = G[Node].begin(); it != G[Node].end(); ++ it)
        if(!Used[it -> first])
            DFS(it -> first, Node, it -> second, L + 1);
}

void BuildAnc()
{
    for(int i = 1; (1 << i) <= N; ++ i)
        for(int j = 1; j <= N; ++ j)
        {
            Anc[i][j] = Anc[i - 1][Anc[i - 1][j]];
            Min[i][j] = min(Min[i - 1][j], Min[i - 1][Min[i - 1][j]]);
        }
}

int GetMin(int X, int Y)
{
    if(Level[X] < Level[Y]) swap(X, Y);
    int StepX, StepY, Ans = INF;
    for(StepX = 1; (1 << StepX) < Level[X]; StepX ++);
    for(StepY = 1; (1 << StepY) < Level[Y]; StepY ++);
    for(; StepX >= 0; StepX --)
        if(Level[X] - (1 << StepX) >= Level[Y])
        {
            Ans = min(Ans, Min[StepX][X]);
            X = Anc[StepX][X];
        }

    if(X == Y) return Ans;

    for(; StepY >= 0; StepY --)
        if(Anc[StepY][X] && Anc[StepY][X] != Anc[StepY][Y])
        {
            Ans = min(Ans, Min[StepY][X]);
            Ans = min(Ans, Min[StepY][Y]);
            X = Anc[StepY][X];
            Y = Anc[StepY][Y];
        }

    Ans = min(Ans, Min[0][X]);
    Ans = min(Ans, Min[0][Y]);
    return Ans;
}

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

    scanf("%i %i %i", &N, &M, &P);
    for(int i = 2; i <= N; ++ i)
    {
        Y = i;
        scanf("%i %i", &X, &V);
        G[X].push_back(make_pair(Y, V));
        G[Y].push_back(make_pair(X, V));
    }
    scanf("%i %i %i %i %i %i", &X, &Y, &A, &B, &C, &D);

    DFS(1, 0, 1, 0);
    BuildAnc();

    for(int i = 1; i <= M; ++ i)
    {
        int Ans = 0;
        if(X != Y) Ans = GetMin(X, Y);
        if(i >= M - P + 1) printf("%i\n", Ans);
        int XP = (X * A + Y * B) % N + 1, YP = (Y * C + Ans * D) % N + 1;
        X = XP;
        Y = YP;
    }

    return 0;
}