Cod sursa(job #1837496)

Utilizator LizaSzabo Liza Liza Data 29 decembrie 2016 19:34:02
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");

const int Nmax = 32005;
int N, M, P, A, B, C, D, X, Y, LCA[25][Nmax], Log[Nmax], Use[Nmax], Level[Nmax], Dist[25][Nmax], dist, Sol[500005], nr;
vector < pair <int, int> > G[Nmax];

void Read()
{
    fin>>N>>M>>P;
    for(int i=2; i<=N; i++)
    {
        int U,V;
        fin>>U>>V;
        G[U].push_back(make_pair(i,V));

    }
    fin>>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;
        int cost = G[nod][i].second;
        if(!Use[vecin])
        {
            Level[vecin] = Level[nod]+1;
            LCA[0][vecin] = nod;
            Dist[0][vecin] = cost;
            DFS(vecin);
        }
    }
}

void Precalculate()
{
    DFS(1);
    for(int i = 2; i <= N; i++) Log[i] = Log[i/2]+1;
    for(int i = 1; i <= Log[N]; i++)
        for(int j = 1; j <= N; j++)
        {
            LCA[i][j] = LCA[i-1][LCA[i-1][j]];
            Dist[i][j] = min(Dist[i-1][j], Dist[i-1][LCA[i-1][j]]);
        }
}

int Stramos(int q, int p)
{
    while(p)
    {
        int k = Log[p];
        dist = min(dist, Dist[k][q]);
        q = LCA[k][q];
        p = p-(1<<k);
    }
    return q;
}

void Solve()
{
    while(M--)
    {
        int xx = X, yy = Y;
        dist = 10000000;
        if(Level[X] < Level[Y]) swap(X,Y);
        int da = Level[X] - Level[Y];
        X=Stramos(X,da);
        for(int i = Log[Level[X]]; i >= 0; i--)
        {
            if(LCA[i][X]!= LCA[i][Y])
            {
                dist = min(dist, min(Dist[i][X],Dist[i][Y]));
                X= LCA[i][X];
                Y= LCA[i][Y];
            }
        }
        if(X!=Y) dist = min(dist, min(Dist[0][X], Dist[0][Y]));
        if(dist == 10000000) dist = 0;
        Sol[++nr] = dist;
        X =(xx*A + yy*B)%N + 1;
        Y =(yy*C + dist*D)%N + 1;
    }
    for(int i = nr-P+1; i <= nr; i++) fout<<Sol[i]<<'\n';
}

int main()
{
    Read();
    Precalculate();
    Solve();
    return 0;
}