Pagini recente » Cod sursa (job #1671867) | Cod sursa (job #876289) | Cod sursa (job #628476) | Cod sursa (job #772464) | Cod sursa (job #973133)
Cod sursa(job #973133)
#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;
}