Cod sursa(job #794690)

Utilizator vendettaSalajan Razvan vendetta Data 6 octombrie 2012 20:28:22
Problema Atac Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.36 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

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

#define nmax 32006
#define inf (1<<30)
#define ll long long
#define Logn 16

int n, m, P, X, Y, A, B, C, D;
vector<pair<int,int> > gf[nmax];
int nivel[nmax], Min[Logn][nmax], tata[Logn][nmax];
bool viz[nmax];

void citeste(){

	f >> n >> m >> P;
	for(int i=2; i<=n; ++i){
        int x, y, cost;
        f >> x >> cost;
        gf[x].push_back(make_pair(i, cost));
        gf[i].push_back(make_pair(x, cost));
	}

    f >> X >> Y >> A >> B >> C >> D;

}

void dfs(int nod, int niv){

    viz[nod] = 1;
    nivel[nod] = niv;

    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){
            tata[0][vc] = nod;
            Min[0][vc] = cost;
            dfs(vc, niv+1);
        }
    }

}

void fa_tati(){

    Min[0][1] = inf;

    for(int i=1; i<Logn; ++i){
        for(int j=1; j<=n; ++j){
            int X = tata[i-1][j];
            tata[i][j] = tata[i-1][X];
            Min[i][j] = min(Min[i-1][j], Min[i-1][X]);
        }
    }

}

void adu_la_acelasi_nivel(int &x, int &y){

    if (nivel[x] == nivel[y]) return;

    if (nivel[x] < nivel[y]) swap(x,y);
    //acum il aduc pe x la nivelul lui y;
    int dif_nivel = nivel[x] - nivel[y];
    for(int i=Logn-1; i>=0; --i){
        if( (dif_nivel & (1<<i) ) != 0 ){
            x = tata[i][x];
        }
    }

}

int afla_lca(int x, int y){

    //presuspun tot timpul ca nodul x il aduc la nivelul nodlui y;
    adu_la_acelasi_nivel(x,y);

    if (x == y) return x;

    //acum practic caut primele noduri ale lui x, y(primele adica chiar dedesubtul Lca-ului) care nu sunt Lca
    for(int i=Logn-1; i>=0; --i){
        if (tata[i][x] == 0) continue;//daca nu asa de sus tata
        if (tata[i][x] == tata[i][y]) continue;//daca au deja acelasi tata
        x = tata[i][x];
        y = tata[i][y];
    }

    return tata[0][x];

}

int afla_muchie_minima(int x, int y, int lca){

    int rez = inf;
    int k = nivel[x] - nivel[lca];//imi al cate-lea tata a lui x e lca

    //fac pt x
    for(int i=Logn-1; i>=0; --i){
        if ( (k & (1<<i) ) != 0 ){
            rez = min(rez, Min[i][x]);//iau minimul de pe intervalul de tati x, x+2^i
            x = tata[i][x];// acum x o sa devina al x+2^i -lea tata
        }
    }

    k = nivel[y] - nivel[lca];
    for(int i=Logn-1; i>=0; --i){
        if ( (k & (1<<i)) != 0 ){
            rez = min(rez, Min[i][y]);
            y = tata[i][y];
        }
    }

    return rez;

}

void rezolva(){

    //am m perechi de forma x,y; eu trebuie sa afisez muchia minima de pe drumul dintre x, y
    //lca-ul il aflu in log n si muchie minima in log n => m * log n

    dfs(1,0);
    fa_tati();


    for(int i=1; i<=m; ++i){
        //aflu lca-ul
        int xx = X;
        int yy = Y;
        int Lca = afla_lca(xx, yy);
        int rez = afla_muchie_minima(xx, yy, Lca);
        if (X == Y) rez = 0;
        X = (X * A + Y * B ) % n + 1;
        Y = (Y * C + rez * D) % n + 1;
        if (i > m-P)
            g << rez << "\n";
    }

}

int main(){

    citeste();
    rezolva();

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

    return 0;

}