Pagini recente » Cod sursa (job #1362846) | Cod sursa (job #3168957) | Cod sursa (job #2813424) | Cod sursa (job #516048) | Cod sursa (job #985645)
Cod sursa(job #985645)
#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;
}