Pagini recente » Cod sursa (job #1356405) | Cod sursa (job #1699722) | Cod sursa (job #1876929) | Cod sursa (job #916924) | Cod sursa (job #794690)
Cod sursa(job #794690)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
using namespace std;
ifstream f("atac.in");
ofstream g("atac.out");
#define nmax 32006
#define inf (1<<30)
#define ll long long
#define Logn 16
int n, m, P, X, Y, A, B, C, D;
vector<pair<int,int> > gf[nmax];
int nivel[nmax], Min[Logn][nmax], tata[Logn][nmax];
bool viz[nmax];
void citeste(){
f >> n >> m >> P;
for(int i=2; i<=n; ++i){
int x, y, cost;
f >> x >> cost;
gf[x].push_back(make_pair(i, cost));
gf[i].push_back(make_pair(x, cost));
}
f >> X >> Y >> A >> B >> C >> D;
}
void dfs(int nod, int niv){
viz[nod] = 1;
nivel[nod] = niv;
for(int i=0; i<gf[nod].size(); ++i){
int vc = gf[nod][i].first;
int cost = gf[nod][i].second;
if (viz[vc] == 0){
tata[0][vc] = nod;
Min[0][vc] = cost;
dfs(vc, niv+1);
}
}
}
void fa_tati(){
Min[0][1] = inf;
for(int i=1; i<Logn; ++i){
for(int j=1; j<=n; ++j){
int X = tata[i-1][j];
tata[i][j] = tata[i-1][X];
Min[i][j] = min(Min[i-1][j], Min[i-1][X]);
}
}
}
void adu_la_acelasi_nivel(int &x, int &y){
if (nivel[x] == nivel[y]) return;
if (nivel[x] < nivel[y]) swap(x,y);
//acum il aduc pe x la nivelul lui y;
int dif_nivel = nivel[x] - nivel[y];
for(int i=Logn-1; i>=0; --i){
if( (dif_nivel & (1<<i) ) != 0 ){
x = tata[i][x];
}
}
}
int afla_lca(int x, int y){
//presuspun tot timpul ca nodul x il aduc la nivelul nodlui y;
adu_la_acelasi_nivel(x,y);
if (x == y) return x;
//acum practic caut primele noduri ale lui x, y(primele adica chiar dedesubtul Lca-ului) care nu sunt Lca
for(int i=Logn-1; i>=0; --i){
if (tata[i][x] == 0) continue;//daca nu asa de sus tata
if (tata[i][x] == tata[i][y]) continue;//daca au deja acelasi tata
x = tata[i][x];
y = tata[i][y];
}
return tata[0][x];
}
int afla_muchie_minima(int x, int y, int lca){
int rez = inf;
int k = nivel[x] - nivel[lca];//imi al cate-lea tata a lui x e lca
//fac pt x
for(int i=Logn-1; i>=0; --i){
if ( (k & (1<<i) ) != 0 ){
rez = min(rez, Min[i][x]);//iau minimul de pe intervalul de tati x, x+2^i
x = tata[i][x];// acum x o sa devina al x+2^i -lea tata
}
}
k = nivel[y] - nivel[lca];
for(int i=Logn-1; i>=0; --i){
if ( (k & (1<<i)) != 0 ){
rez = min(rez, Min[i][y]);
y = tata[i][y];
}
}
return rez;
}
void rezolva(){
//am m perechi de forma x,y; eu trebuie sa afisez muchia minima de pe drumul dintre x, y
//lca-ul il aflu in log n si muchie minima in log n => m * log n
dfs(1,0);
fa_tati();
for(int i=1; i<=m; ++i){
//aflu lca-ul
int xx = X;
int yy = Y;
int Lca = afla_lca(xx, yy);
int rez = afla_muchie_minima(xx, yy, Lca);
if (X == Y) rez = 0;
X = (X * A + Y * B ) % n + 1;
Y = (Y * C + rez * D) % n + 1;
if (i > m-P)
g << rez << "\n";
}
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}