Cod sursa(job #789422)

Utilizator vendettaSalajan Razvan vendetta Data 17 septembrie 2012 23:11:44
Problema Atac Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.1 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 ll long long
#define inf (1<<30)

int n, m, p;
vector<pair<int,int> > gf[nmax];

int tata[16][nmax], Min[16][nmax];

int aint[4*nmax*2], v[2*nmax], nivel[nmax], P[nmax];
bool viz[nmax];

int X, Y, A, B, C, D;

void citeste(){

	f >> n >> m >> p;//numarul de noduri; numarul de query-uri si P ultimele P query-uri trebuie sa le afisez
    for(int i=2; i<=n; ++i){
        int x, cost;
        f >> x >> cost;//am muchie intre x si i cu costul cost
        gf[x].push_back( make_pair(i,cost) );
        //gf[i].push_back( make_pair(x,cost) );
    }

    f >> X >> Y >> A >> B >> C >> D;//prima perechec si apoi A, B ,C, D niste variabile care o sa ma ajute sa o aflu pe urmatoare pereche

}

void initializeaza(int vc, int nod, int cost){

    //initializez matricile tata si Min
    tata[0][vc] = nod;//primul tata al lui vecin e nod
    Min[0][vc] = cost;//costul de pe acest drum evident va fi costul muchie care ii leaga

}

void euler(int nod, int niv){

    viz[nod] = 1;
    v[ ++v[0] ]  = nod;//nodul de pe pozitia v[0] din parcurgerea euleriana
    nivel[ nod ] = niv;//nivelul nodului in parcugere
    P[nod] = v[0];//prima aparitie a nodului in parcugrerea euleriana(am nevoie de ea pt LCA);

    for(int i=0; i<gf[nod].size(); ++i){
        int vc = gf[nod][i].first;
        int cost = gf[nod][i].second;//costul de la nod la vc
        if (viz[vc] == 1) continue; // daca l-am vizitat dja
        initializeaza(vc, nod, cost);//initializez matriciele tata si Min pt muchia nod->vc
        euler(vc, niv+1);
        v[ ++v[0] ] = nod;
    }

}

void build(int nod, int st, int dr){

    if (st == dr){
        aint[nod] = st;
        return;
    }

    int mij = (st + dr) / 2;
    build(nod*2, st, mij);//construiesc fiul stang
    build(nod*2+1, mij+1, dr);//fiul drept

    aint[nod] = aint[nod*2];
    if (nivel[ v[ aint[nod] ] ] > nivel[ v[ aint[nod*2+1] ] ]){
        aint[nod] = aint[nod*2+1];
    }

}

void preprocesare(){

    //tata[i][nod] = al 2 ^ ilea tata a lui nod
    //Min[i][nod] = muchia minima de pe drumul nod, 2^i-lea tata

    //am initializizat pentru al 2 ^ 0 tata pentru fiecare nod in parcurgearea euleriana
    // imi ajunge 15 ; 2^ 15 >= nmax
    Min[0][1] = inf;

    for(int i=1; i<=15; ++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 query(int nod, int st, int dr, int a, int b, int &_min){

    if (a <= st && dr <= b){
        if ( _min > nivel[ v[ aint[nod] ] ] ){
            _min = nivel[ v[ aint[nod] ] ];
        }
        return;
    }

    int mij = (st + dr) / 2;

    if (a <= mij) query(nod*2, st, mij, a, b, _min);
    if (b > mij) query(nod*2+1, mij+1, dr, a, b, _min);

}

int afla_min(int nod, int k){

    //trebuie sa aflu muchia minima de pe drum nod - al k -lea tata a lui nod

    int _min = inf;

    for(int i=15; i>=0; --i){
        if ( ( k & (1<<i) ) != 0 ){//daca am 1 pe pozitia i in k
            _min = min(_min, Min[i][nod]);
            nod = tata[i][nod];
        }
    }

    return _min;

}

int fa_solutie(int nod, int lca_nivel){

    //nod = nodul din care vrea sa ma duc in sus pana la lca
    //nivel = nivelul pe care se afla lca
    // = > tatal pe care trebuie sa il caut = nivel[nod] - lca_nivel;
    int k = nivel[nod] - lca_nivel;

    return (afla_min(nod, k));

}

void rezolva(){

    //am o pereche x, y trebuie sa afisez muchia minima de pe drum dintre x si y;
    //o imparte in 2 etape : aflu lca celor 2 noduri si calculez muchia minim de pe drumul x, lca si y, lca
    //ma folosesc de ideea de la stramosi

    //fac o parcugere euleriana a arboreluri fixand radacina in 1
    euler(1,0);

    build(1, 1, v[0]);//construiesc arborele de intervale

    preprocesare();

    for(int i=1; i<=m; ++i){
        int x = P[X];//prima aparitie a lui x
        int y = P[Y];//prima aparitie a lui y
        if (x > y) swap(x,y);//daca y apare in fata lui x in parcurgea euleriana; ii schimb
        int Lca = 0;
        int min_nivel = inf;
        query(1, 1, v[0], x, y, min_nivel);
        //am aflat lca celor 2

        //aflu muchia minim dintre X si Lca
        //acum trebuie sa aflu al catelea tata e Lca => Lca e nivelul_lca_in arbore - nivelul_X_in arbore
        int rez = inf;

        rez = min( rez, fa_solutie(X, min_nivel) );
        rez = min( rez, fa_solutie(Y, min_nivel) );

        if (X == Y) rez = 0 ;//daca cele doua coincid(zice la restrictii)

        if (i > m-p) g << rez << "\n";
        //X' = (X*A + Y*B) mod N + 1
        //Y' = (Y*C + Z*D) mod N + 1
        X = (X * A + Y * B ) % n + 1;
        Y = (Y * C + rez * D) % n + 1;
    }

}

int main(){

    citeste();
    rezolva();

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

    return 0;

}