Pagini recente » Cod sursa (job #2680744) | Cod sursa (job #862481) | Cod sursa (job #2402828) | Cod sursa (job #189197) | Cod sursa (job #926918)
Cod sursa(job #926918)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define nmax 32005
#define Logmax 16
#define inf (1<<30)
ifstream f("atac.in");
ofstream g("atac.out");
int n, m, p, X, Y, A, B, C, D, Muchie[Logmax][nmax], Tata[Logmax][nmax];
int Rmq[Logmax][nmax*2], Nod[Logmax][nmax*2];
int t[nmax], secv[nmax*2], P[nmax], nivel[nmax];
bool viz[nmax];
vector< pair<int,int> > gf[nmax];
int Log[nmax*2];
void citeste(){
f >> n >> m >> p;
int u, v;
for(int i=2; i<=n; ++i){
f >> u >> v;
gf[i].push_back( make_pair(u, v) );
gf[u].push_back( make_pair(i, v));
}
f >> X >> Y >> A >> B >> C >> D;
}
void init(int nod, int tata, int cost){
Muchie[0][nod] = cost;
Tata[0][nod] = tata;
}
void dfs(int nod){
viz[nod] = 1;
secv[++secv[0]] = nod;
P[nod] = secv[0];
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){
t[vc] = nod;
init(vc, nod, cost);
nivel[vc] = nivel[nod] + 1;
dfs(vc);
secv[ ++secv[0] ] = nod;
}
}
}
void bagaRmqLca(){
for(int i=1; i<=secv[0]; ++i) Rmq[0][i] = nivel[ secv[i] ], Nod[0][i] = secv[i];
for(int i=1; i<Logmax; ++i){
for(int j=1; j+(1<<i)-1 <= secv[0]; ++j){
Rmq[i][j] = Rmq[i-1][j];
Nod[i][j] = Nod[i-1][j];
int dr = j + (1<<i) - 1;
int newJ = dr - (1<<(i-1)) + 1;
if (Rmq[i][j] > Rmq[i-1][newJ]){
Rmq[i][j] = Rmq[i-1][newJ];
Nod[i][j] = Nod[i-1][newJ];
}
}
}
}
void bagaMuchieMin(){
for(int i=1; i<Logmax; ++i){
for(int j=1; j<=n; ++j){
int oldJ = Tata[i-1][j];
Tata[i][j] = Tata[i-1][oldJ];
Muchie[i][j] = min(Muchie[i-1][j], Muchie[i-1][oldJ]);
}
}
}
inline int aflaLca(int x, int y){
int lung = y - x + 1;
int Min = inf; int Lca = 0;
int k = Log[lung];
Min = Rmq[k][x];
Lca = Nod[k][x];
int newX = y - (1<<k) + 1;
if (Min > Rmq[k][newX]){
return Nod[k][newX];
}
return Lca;
}
void debug(){
for(int i=1; i<=secv[0]; ++i) cout << secv[i] << " ";
cout << "\n";
for(int i=1; i<=secv[0]; ++i) cout << nivel[ secv[i] ] << " ";
cout << "\n";
for(int i=1; i<=secv[0]; ++i) cout << i <<" " ;
cout << "\n";
}
inline int MuchieMin(int x, int Lca){
int Dist = nivel[x] - nivel[Lca];
int Rez = inf;
for(int i=Logmax-1; i>=0; --i){
if (Dist & (1<<i)){
Rez = min(Rez, Muchie[i][x]) ;
x = Tata[i][x];
}
}
return Rez;
}
inline int aflaMuchie(int x, int y, int Lca){
return min( MuchieMin(x, Lca), MuchieMin(y, Lca) );
}
void rezolva(){
// muchia minima de pe drumul de la X la Y; il impart in muchia miima de la X la Lca Y la lca
dfs(1);
bagaRmqLca();
bagaMuchieMin();
//debug();
Log[1] = 0; for(int i=2; i<=secv[0]; ++i) Log[i] = Log[i/2] + 1;
//X' = (X*A + Y*B) mod N + 1
//Y' = (Y*C + Z*D) mod N + 1
for(int i=1; i<=m; ++i){
int px = P[X]; int py = P[Y];
if (px > py) swap(px, py);
int Lca = aflaLca (px, py);
//cout << Lca << "\n";
int Rez = aflaMuchie(X, Y, Lca);
if (X == Y) Rez = 0;
if (i >= m-p)
g << Rez<< "\n";
//g << Rez<< "\n";
X = (X*A + Y*B) % n + 1;
Y = (Y*C + Rez*D) % n + 1;
}
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}