Cod sursa(job #973133)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 13 iulie 2013 15:42:15
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.26 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <utility>
#include <string.h>
#include <math.h>
using namespace std;

ifstream cin("atac.in");
ofstream cout("atac.out");

const int MAXN = 32005>>1;
const int oo = (1<<31)-1;
const int MAXL = 20;

typedef vector<int> Graph[MAXN];
typedef vector<int> :: iterator It;

Graph G;
int n, m, p, K;
int Euler[MAXN>>1], Level[MAXN>>1], LVL[MAXN], RMQ[MAXL][MAXN>>2],
    First[MAXN], Lg[MAXN>>1], Bombs[MAXN], Father[MAXN], Q[MAXL][MAXN], D[MAXL][MAXN];

inline void DFs(int Node, int ActLevel){
    Euler[++K] = Node; ///Aduag nodul curent la Parcurgerea Euler
    First[Node] = K; /// Retin pozitia de inceput a Nodului Node in parcurgerea Euler
    Level[K] = ActLevel; /// Levelul nodului de pe pozitia k in parcuregerea euler
    LVL[Node] = ActLevel; /// Retin si Level-ul fiecarui Nod ca sa nu ma complic mai incolo cu un alt dfs.
    for(It it = G[Node].begin(), fin = G[Node].end() ; it != fin ; ++ it){
        DFs(*it, ActLevel + 1);
        Euler[++K] = Node;    ///idem
        Level[K] = ActLevel;
    }
}

inline void Build_Log(){
    for(int i = 2 ; i <= K ; ++ i)
        Lg[i] = Lg[i>>1] + 1;
}

inline void Build_RMQ(){
    for(int i = 1 ; i <= K ; ++ i)
        RMQ[0][i] = i;
    for(int i = 1 ; (1<<i) <= K ; ++ i)
        for(int j = 1 ; j <= K - (1<<i) + 1 ; ++ j){
            int l = 1 << (i-1);
            RMQ[i][j] = RMQ[i-1][j];
            if(Level[RMQ[i][j]] > Level[RMQ[i-1][j+l]])
                RMQ[i][j] = RMQ[i-1][j+l];
        }
}

inline int Lca(int X, int Y){
    X = Level[X];
    Y = Level[Y];
    if( X > Y )
        swap(X, Y);
    int diff = Y - X + 1;
    int log = Lg[diff];
    int Ans = RMQ[log][X];
    int sh = diff - ( 1 << log );
    if(Level[Ans] > Level[RMQ[log][X+sh]])
        Ans = RMQ[log][X+sh];
    return Euler[Ans];
}

inline void Build_Stramosi(){
    for(int i = 2 ; i <= n ; ++ i)
        Q[0][i] = Father[i] , D[0][i] = Bombs[i];
    for(int i = 1; (1<<i) <= n ; ++ i)
        for(int j = 1 ; j <= n ; ++ j){
            if( (1<<i) < LVL[j] )
            Q[i][j] = Q[i-1][Q[i-1][j]];
            D[i][j] = D[i-1][j];
            if(D[i-1][Q[i-1][j]] < D[i][j])
                D[i][j] = D[i-1][Q[i-1][j]];
        }
}
inline int Query (int X, int Y){
    int diff = LVL[X] - LVL[Y], Ans = oo;
    for (int i = 0; (1 << i) <= diff; ++ i)
        if (diff & (1 << i)){
            if (D[i][X] < Ans)
                Ans = D[i][X];
            X = Q[i][X];
        }
    return Ans;
}

int main(){
    cin >> n >> m >> p;
    for(int i = 2 ; i <= n ; ++ i){
        int x, y;
        cin >> Father[i] >> Bombs[i];
        G[Father[i]].push_back(i);
    }
    Bombs[1] = oo;
    DFs(1, 0);
    Build_Log();
    Build_RMQ();
    Build_Stramosi(); ///prima aplicabilitate
    int X, Y, Z, A, B, C, D;
    int i = 1;
    for(cin >> X >> Y >> A >> B >> C >> D; m ; -- m){
        int LCA = Lca(X, Y)*(X == Y);
        Z = min(Query(X, LCA), Query(Y, LCA));
        if(m <= p)
            cout << Z << "\n";
        int Xx = (X*A + Y*B)%n + 1;
        int Yy = (Y*C + Z*D)%n + 1;
        X = Xx;
        Y = Yy;
    }
    cin.close();
    cout.close();
    return 0;
}