Cod sursa(job #2181139)

Utilizator CriogeniXBociat Daniel Tiberiu CriogeniX Data 21 martie 2018 14:29:46
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

const int NMax = 32005;
const int oo = 20000000;

int N, M, P;
int A,B,C,D, X, Y, Z;
int lca;
int T[20][NMax], CM[20][NMax], Level[NMax], Log[NMax];
bool Use[NMax];
vector <pair<int, int>> G[NMax];

void Read()
{
    in >> N >> M >> P;
    for(int i = 2; i<=N;++i)
    {
        int x,y;
        in >> x >> y;
        G[x].push_back(make_pair(i,y));
        G[i].push_back(make_pair(x,y));
    }
    in >> X >> Y >> A >> B >> C >> D;
}

void DFS(int Nod)
{
    Use[Nod] = 1;
    for(int i = 0; i < (int)G[Nod].size(); ++i)
    {
        int Vecin = G[Nod][i].first;
        if(!Use[Vecin])
        {
            T[0][Vecin] = Nod;
            CM[0][Vecin] = G[Nod][i].second;
            Level[Vecin] = Level[Nod] + 1;
            DFS(Vecin);
        }
    }
}

int LCA(int x,int y)
{
    if(Level[x]<Level[y])
            swap(x,y);

    while(Level[x] != Level[y])
    {
        int K = Log[Level[x]-Level[y]];
        x = T[K][x];
    }

    if(x==y)
        return x;

    for(int i = Log[Level[x]]; i >= 0 ; i--)
    {
        if(T[i][x]!=T[i][y])
        {
            x = T[i][x];
            y = T[i][y];
        }
    }

    return T[0][x];
}

int Solve(int x, int y)
{
    if(x == y)
        return oo;
    int d = Log[Level[x] - Level[y]]; //cand apelam y = lca => level mai mic
    if(Level[T[d][x]] == Level[y])
        return CM[d][x];
    else
        return min(CM[d][x], Solve(T[d][x],y));
}

int main()
{
    Read();
    Level[1] = 1;
    DFS(1);

    for(int i = 1 ; 1<<i <= N ; ++i)
    {
        for(int j = 1 ; j <= N ; ++j)
        {
            T[i][j] = T[i-1][T[i-1][j]];
            if(T[i][j])
                CM[i][j] = min(CM[i-1][j],CM[i-1][T[i-1][j]]);
        }
    }
    for(int i = 2; i <= N ; ++i)
        Log[i] = Log[i/2]+1;
    while(M--)
    {
        if(X==Y)
            Z=0;
        else
        {
            lca = LCA(X,Y);
            Z = min(Solve(X,lca),Solve(Y,lca));
        }
        if(M < P)
            out << Z << '\n';
        X=(X*A+Y*B)%N+1;
        Y=(Y*C+Z*D)%N+1;
    }
    return 0;
}