Cod sursa(job #985645)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 17 august 2013 12:56:31
Problema Atac Scor 100
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;
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<<1], D[MAXL][MAXN<<1];
 
inline void DFs(int Node, int ActLevel){
    Euler[++K] = Node;      
    First[Node] = K;        
    Level[K] = ActLevel;    
    LVL[Node] = ActLevel;    
    for(It it = G[Node].begin(), fin = G[Node].end() ; it != fin ; ++ it){
        DFs(*it, ActLevel + 1);
        Euler[++K] = Node;  
        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){
    int A = First[X];
    int B = First[Y];
    if( A > B )
        swap(A, B);
    int diff = B - A + 1;
    int log = Lg[diff];
    int Ans = RMQ[log][A];
    int sh = diff - ( 1 << log );
    if(Level[Ans] > Level[RMQ[log][A+sh]])
        Ans = RMQ[log][A+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;
}
 
inline void Debug(){
    for(int i = 1 ; i <= m ; ++ i){
        int x, y;
        cin >> x >> y;
        cout << Lca(x, y) << '\n';
    }
}
 
int main(){
    cin >> n >> m >> p;
    for(int i = 2 ; i <= n ; ++ i){
        cin >> Father[i] >> Bombs[i];
        G[Father[i]].push_back(i);
    }
    Bombs[1] = oo;
    DFs(1, 1);
    Build_Log();
    Build_RMQ();
    Build_Stramosi(); ///prima aplicabilitate
    int X, Y, Z, A, B, C, D;
    for(cin >> X >> Y >> A >> B >> C >> D; m ; -- m){
        int LCA = Lca(X, Y);
        Z = min(Query(X, LCA), Query(Y, LCA))*(X != Y);
        //cout << X << " " << Y << " " << Z << '\n';
        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;
    }
    /* Debug() */
 
    cin.close();
    cout.close();
    return 0;
}