Cod sursa(job #926919)

Utilizator vendettaSalajan Razvan vendetta Data 25 martie 2013 14:10:49
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.72 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

#define nmax 32005
#define Logmax 16
#define inf (1<<30)

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

int n, m, p, X, Y, A, B, C, D, Muchie[Logmax][nmax], Tata[Logmax][nmax];
int Rmq[Logmax][nmax*2], Nod[Logmax][nmax*2];
int t[nmax], secv[nmax*2], P[nmax], nivel[nmax];
bool viz[nmax];
vector< pair<int,int> > gf[nmax];
int Log[nmax*2];

void citeste(){
    f >> n >> m >> p;
    int u, v;
    for(int i=2; i<=n; ++i){
        f >> u >> v;
        gf[i].push_back( make_pair(u, v) );
        gf[u].push_back( make_pair(i, v));
    }
    f >> X >> Y >> A >> B >> C >> D;
}

void init(int nod, int tata, int cost){
    Muchie[0][nod] = cost;
    Tata[0][nod] = tata;
}

void dfs(int nod){
    viz[nod] = 1;
    secv[++secv[0]] = nod;
    P[nod] = secv[0];

    for(int i=0; i<gf[nod].size(); ++i){
        int vc = gf[nod][i].first;
        int cost = gf[nod][i].second;
        if (viz[vc] == 0){
            t[vc] = nod;
            init(vc, nod, cost);
            nivel[vc] = nivel[nod] + 1;
            dfs(vc);
            secv[ ++secv[0] ] = nod;
        }
    }
}

void bagaRmqLca(){
    for(int i=1; i<=secv[0]; ++i) Rmq[0][i] = nivel[ secv[i] ], Nod[0][i] = secv[i];

    for(int i=1; i<Logmax; ++i){
        for(int j=1; j+(1<<i)-1 <= secv[0]; ++j){
            Rmq[i][j] = Rmq[i-1][j];
            Nod[i][j] = Nod[i-1][j];
            int dr = j + (1<<i) - 1;
            int newJ = dr - (1<<(i-1)) + 1;
            if (Rmq[i][j] > Rmq[i-1][newJ]){
                Rmq[i][j] = Rmq[i-1][newJ];
                Nod[i][j] = Nod[i-1][newJ];
            }
        }
    }
}

void bagaMuchieMin(){
    for(int i=1; i<Logmax; ++i){
        for(int j=1; j<=n; ++j){
            int oldJ = Tata[i-1][j];
            Tata[i][j] = Tata[i-1][oldJ];
            Muchie[i][j] = min(Muchie[i-1][j], Muchie[i-1][oldJ]);
        }
    }
}

inline int aflaLca(int x, int y){
    int lung = y - x + 1;
    int Min = inf; int Lca = 0;
    int k = Log[lung];
    Min = Rmq[k][x];
    Lca = Nod[k][x];
    int newX = y - (1<<k) + 1;
    if (Min > Rmq[k][newX]){
        return Nod[k][newX];
    }
    return Lca;
}

void debug(){
    for(int i=1; i<=secv[0]; ++i) cout << secv[i] << " ";
    cout << "\n";
    for(int i=1; i<=secv[0]; ++i) cout << nivel[ secv[i] ] << " ";
    cout << "\n";
    for(int i=1; i<=secv[0]; ++i) cout << i <<" " ;
    cout << "\n";
}

inline int MuchieMin(int x, int Lca){
    int Dist = nivel[x] - nivel[Lca];
    int Rez = inf;
    for(int i=Logmax-1; i>=0; --i){
        if (Dist & (1<<i)){
            Rez = min(Rez, Muchie[i][x]) ;
            x = Tata[i][x];
        }
    }
    return Rez;
}

inline int aflaMuchie(int x, int y, int Lca){
    return min( MuchieMin(x, Lca), MuchieMin(y, Lca) );
}

void rezolva(){
    // muchia minima de pe drumul de la X la Y; il impart in muchia miima de la X la Lca Y la lca
    dfs(1);
    bagaRmqLca();
    bagaMuchieMin();

    //debug();

    Log[1] = 0; for(int i=2; i<=secv[0]; ++i) Log[i] = Log[i/2] + 1;

    //X' = (X*A + Y*B) mod N + 1
    //Y' = (Y*C + Z*D) mod N + 1

    for(int i=1; i<=m; ++i){
        int px = P[X]; int py = P[Y];
        if (px > py) swap(px, py);
        int Lca = aflaLca (px, py);
        //cout << Lca << "\n";

        int Rez = aflaMuchie(X, Y, Lca);
        if (X == Y) Rez = 0;
        if (i >= m-p+1)
        g << Rez<< "\n";
        //g << Rez<< "\n";

        X = (X*A + Y*B) % n + 1;
        Y = (Y*C + Rez*D) % n + 1;
    }
}

int main(){
    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;
}