Cod sursa(job #789421)

Utilizator vendettaSalajan Razvan vendetta Data 17 septembrie 2012 23:03:32
Problema Atac Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.49 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[20][nmax], Min[20][nmax];

int aint[4*nmax*2], v[2*nmax], nivel[nmax*2], P[nmax], dist[nmax];
bool viz[nmax];
int _Min;
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

    for(int i=0; i<=20; ++i) for(int j=0; j<=n; ++j) Min[i][j] = inf;

}

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;
    dist[nod] = niv;
    v[ ++v[0] ]  = nod;//nodul de pe pozitia v[0] din parcurgerea euleriana
    nivel[ v[0] ] = 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] == 0) { // daca l-am vizitat dja
        //t[vc] = cost;//tin minte cat ma cost sa ma duc de la vc la tata(evident o sa ma pot duce doar pe una)
        //initializeaza(vc, nod, cost);//initializez matriciele tata si Min pt muchia nod->vc
        Min[0][vc] = gf[nod][i].second;
        tata[0][vc] = nod;
        euler(vc, niv+1);
        v[ ++v[0] ] = nod;
        nivel[ v[0] ] = niv;
        }
    }

}

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


    for(int i=1; i<=19; ++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 udpate(int nod, int st, int dr, int poz, int val){

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

    int mij = (st + dr) / 2;
    if (poz <= mij) udpate(nod*2, st, mij, poz, val);
               else udpate(nod*2+1, mij+1, dr, poz, val);

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

}

void query(int nod, int st, int dr, int a, int b){

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

    int mij = (st + dr) / 2;

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

}

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;
    int i = 0;
    while(k){
        if (k & 1){
            _min = min(_min, Min[i][nod]);
            nod = tata[i][nod];
        }
        ++i;
        k = k >> 1;
    }

    return _min;

}

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,1);

    //build(1, 1, v[0]);//construiesc arborele de intervale
    for(int i=1; i<=v[0]; ++i) udpate(1, 1, v[0], i, i);

    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
        _Min = inf;
        query(1, 1, v[0], x, y);
        //am afla 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;

        int k = dist[X] - _Min;
        rez = min(rez, afla_min(X, k) );
        k = dist[Y] - _Min;
        rez = min(rez, afla_min(Y,k) );
        if (X == Y) rez = 0;
        if (rez == inf) rez = 0;
        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;

}