Pagini recente » Cod sursa (job #1622487) | Cod sursa (job #2380427) | Cod sursa (job #2740556) | Cod sursa (job #2255188) | Cod sursa (job #2762539)
/*
Am adaugat ceva la liniile 73-75
*/
/*
Functia minimPeLant la mine face o chestie foarte idioata
nu incercati sa cititi sursa, cautati alta
*/
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 32000 //treizeci si doi de mii
#define LOGMAXN 14 //[ log 2 (32 000) ]
#define INFINIT 100001 //o suta de mii unu
using namespace std;
ifstream fin ("atac.in");
ofstream fout ("atac.out");
int N, M, P;
int REZ; //global!!
int tt[LOGMAXN + 1][NMAX + 1];
int mn[LOGMAXN + 1][NMAX + 1];
int depth[NMAX + 1];
vector <int> fii[NMAX + 1]; //doar ca sa prelucrez depth[]
int putereDoiLowerbound(int VAL){
int lo = -1;
int hi = LOGMAXN + 1; //[ log 2 (NMAX) ] + 1
while(hi - lo > 1){
int mid = lo + (hi - lo) / 2;
if( (1 << mid) <= VAL ){
lo = mid;
}
else {
hi = mid;
}
}
return lo;
}
int nodNouDepth(int nod, int depthNou){
//printf("Il urc pe %d\n", nod);
//printf("nod = %d\n", nod);
while(depth[nod] != depthNou){
//caut binar cea mai mare putere a lui 2 cu care pot sa urc in arbore incat sa nu depasesc depthNou
int urcare = putereDoiLowerbound(depth[nod] - depthNou);
REZ = min(REZ, mn[urcare][nod]);
nod = tt[urcare][nod];
//printf("nod = %d\n", nod);
}
//printf("\n");
return nod;
}
int minimPeLant(int A, int B){
//mai intai vreau sa le aduc la acelasi depth
//printf("Query pe (%d, %d)\n", A, B);
if(A == B){
return 0;
}
REZ = INFINIT;
if(depth[A] > depth[B]){
swap(A, B);
}
B = nodNouDepth(B, depth[A]);
//acum urc cu puteri ale lui 2 pana dau de LCA
while(A != B){
int lo = -1;
int hi = -1 + 1;
for(int i = 0; (1 << i) <= depth[A] - 2; i++){
hi = i + 1;
}
//printf("hi = %d\n", hi);
while(hi - lo > 1){
int mid = lo + (hi - lo) / 2;
int ttA = tt[mid][A];
int ttB = tt[mid][B];
if(ttA == ttB){
hi = mid;
}
else {
lo = mid;
}
}
//printf("(A, B) = (%d, %d)\nUrc cu pas %d\n", A, B, lo);
if(lo == -1){
REZ = min(REZ, mn[0][A]);
REZ = min(REZ, mn[0][B]);
A = tt[0][A];
B = tt[0][B];
}
else {
REZ = min(REZ, mn[lo][A]);
REZ = min(REZ, mn[lo][B]);
A = tt[lo][A];
B = tt[lo][B];
}
}
//printf("Sfarsit query!\n\n");
return REZ;
}
void prelucrareTati(){
for(int j = 1; j <= LOGMAXN; j++){
for(int i = 1; i <= N; i++){
if( (1 << j) - 1 <= depth[i] ){
tt[j][i] = tt[j - 1][ tt[j - 1][i] ];
}
}
}
}
void prelucrareMinim(){
for(int j = 1; j <= LOGMAXN; j++){
for(int i = 1; i <= N; i++){
if( (1 << j) <= depth[i] ){
mn[j][i] = min( mn[j - 1][i], mn[j - 1][ tt[j - 1][i] ] );
}
}
}
}
void DFS(int node){
for(int i = 0; i < fii[node].size(); i++){
int vec = fii[node][i];
depth[vec] = depth[node] + 1;
DFS(vec);
}
}
int main()
{
fin >> N >> M >> P;
tt[0][1] = 1;
mn[0][1] = INFINIT;
for(int i = 2; i <= N; i++){
fin >> tt[0][i] >> mn[0][i];
fii[ tt[0][i] ].push_back(i); //doar pt DFS, pt aflarea depth[]
}
depth[1] = 1;
DFS(1); //aleg 1 ca radacina
prelucrareTati();
prelucrareMinim();
int X, Y, A, B, C, D;
fin >> X >> Y >> A >> B >> C >> D;
for(int question = 1; question <= M; question++){
int raspuns = minimPeLant(X, Y);
if(M - question + 1 <= P){
fout << raspuns << "\n";
}
X = (X * A + Y * B) % N + 1;
Y = (Y * C + raspuns * D) % N + 1;
}
return 0;
}