Cod sursa(job #1295002)

Utilizator RaduVisanRadu Visan RaduVisan Data 18 decembrie 2014 17:25:19
Problema Atac Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;

const int NMAX = 32010, INF = 0x3f3f3f3f;

int N, M, P, U, V, Ancestor[15][NMAX], MinCost[15][NMAX], Level[NMAX], X, Y, A, B, C, D;
vector<pair<int, int> > G[NMAX];
bool Used[NMAX];

void DFS(int Node)
{
    Used[Node] = 1;
    for(int i = 0; i < G[Node].size(); ++ i)
    {
        int Vec = G[Node][i].first, Cost = G[Node][i].second;
        if(Used[Vec]) continue;
        Level[Vec] = Level[Node] + 1;
        Ancestor[0][Vec] = Node;
        MinCost[0][Vec] = Cost;
        DFS(Vec);
    }
}

void Build()
{
    for(int i = 1; (1 << i) <= N; ++ i)
        for(int j = 1; j <= N; ++ j)
        {
            Ancestor[i][j] = Ancestor[i - 1][Ancestor[i - 1][j]];
            MinCost[i][j] = min(MinCost[i - 1][j], MinCost[i - 1][Ancestor[i - 1][j]]);
        }
}

int GetMin(int X, int Y)
{
    if(Level[X] < Level[Y]) swap(X, Y);

    int StepX, StepY, Min = INF;
    for(StepX = 0; (1 << StepX) <= Level[X]; StepX ++);
    for(StepY = 0; (1 << StepY) <= Level[Y]; StepY ++);

    for(; StepX >= 0; StepX --)
        if(Level[X] - (1 << StepX) >= Level[Y])
        {
            Min = min(Min, MinCost[StepX][X]);
            X = Ancestor[StepX][X];
        }

    if(X == Y) return Min;

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

    Min = min(Min, MinCost[0][X]);
    Min = min(Min, MinCost[0][Y]);

    return Min;
}

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)
    {
        scanf("%i %i", &U, &V);
        G[i].push_back(make_pair(U, V));
        G[U].push_back(make_pair(i, V));
    }
    scanf("%i %i %i %i %i %i", &X, &Y, &A, &B, &C, &D);

    Level[1] = 1;
    DFS(1);
    Build();

    for(int i = 1; i <= M; ++ i)
    {
        int Z = GetMin(X, Y);
        int NextX = (1LL * X * A + 1LL * Y * B) % N + 1;
        int NextY = (1LL * Y * C + 1LL * Z * D) % N + 1;
        X = NextX; Y = NextY;

        if(i >= M - P + 1) printf("%i\n", Z);
    }
}