Cod sursa(job #1558628)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 29 decembrie 2015 14:05:50
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#include<fstream>
#include<vector>
#include<iostream>
#include<iterator>

using namespace std;

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

vector <pair <int, int> > G[40000];
int TT[20][40000], Dist[20][40000], Level[40000], Use[40000], Log[40000], Sol[500005];
int n, m, p, a, b, c, d, x, y, dist, k;
int const oo = 10000000;

void citire()
{
    int i;
    f>>n>>m>>p;
    for(i=2; i<=n; i++){
        f>>x>>c;
        G[i].push_back(make_pair(x, c));
        G[x].push_back(make_pair(i, c));
    }
    f>>x>>y>>a>>b>>c>>d;
}

void DFSL(int nod)
{
    Use[nod] = 1;
    int vecin, cost, i;
    vector < pair <int, int> > :: iterator it;
    for(it = G[nod].begin(); it != G[nod].end(); it++){
        vecin = it -> first;
        cost = it -> second;
        if(!Use[vecin]){
            Level[vecin] = Level[nod] + 1;
            TT[0][vecin] = nod;
            Dist[0][vecin] = cost;
            DFSL(vecin);
        }
    }
}

void precalc()
{
    DFSL(1);
    int i, j;

    for(i=2; i<=n; i++)
        Log[i] = Log[i/2] + 1;

    for(i=1; i<=Log[n]; i++)
        for(j=1; j<=n; j++){
            TT[i][j] = TT[i-1][TT[i-1][j]];
            Dist[i][j] = min(Dist[i-1][TT[i-1][j]], Dist[i-1][j]);
        }

}

void ance(int & nod, int p)
{
    int red;
    while(p){
        red = Log[p];
        dist = min(dist, Dist[red][nod]);
        nod = TT[red][nod];
        p -= (1<<red);
    }
}

int rez()
{
    int diff, i, x1, y1;

    while(m--){
        x1 = x;
        y1 = y;
        dist = oo;
        if(Level[x] < Level[y])
            swap(x, y);
        diff = Level[x] - Level[y];
        ance(x, diff);

        for(i = Log[Level[x]]; i >= 0; i--)
            if(TT[i][x] != TT[i][y]){
                dist = min(dist, min(Dist[i][x], Dist[i][y]));
                x = TT[i][x];
                y = TT[i][y];
            }
        if(x != y){
            dist = min(dist, min(Dist[0][x], Dist[0][y]));
        }
        if(dist == oo)
            dist = 0;

        Sol[++k] = dist;

        x = (x1*a + y1*b)%n + 1;
        y = (y1*c + dist*d)%n + 1;
    }

    for(i = k - p + 1; i<=k; i++)
        g<<Sol[i]<<" ";
    g<<"\n";
}

int main()
{
    citire();
    precalc();
    rez();
    return 0;
}