Cod sursa(job #1685843)

Utilizator cordun_cristinaCristina Maria Cordun cordun_cristina Data 11 aprilie 2016 21:26:00
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream f("atac.in");
ofstream g("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()
{
    f>>n>>m>>p;
    for(int i = 2; i <= n; i++)
    {
        int u,v;
        f>>u>>v;
        G[u].push_back(make_pair(i,v));
        //G[i].push_back(make_pair(u,v));
    }
    f>>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]]);
        }
}

void 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);
    }
}

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];
        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++) g<<Sol[i]<<'\n';
}

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