Pagini recente » Cod sursa (job #3162228) | Cod sursa (job #78187) | Cod sursa (job #387604) | Cod sursa (job #2459504) | Cod sursa (job #212408)
Cod sursa(job #212408)
#include <fstream>
#include <vector>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
const int NMAX=32001;
int N,M,P,X,Y,Z,A,B,C,D,nr;
int s[32][NMAX];//s[j][[i]=al 2^j -lea stramos al lui i
int m[32][NMAX];//m[j][i]=minimul pe drumul de la i la al 2^j stramos al lui i
int rmq[33][2*NMAX],v[2*NMAX],log[2*NMAX];
int niv[NMAX],poz[NMAX];
vector< pair<int,int> > G[NMAX];
ifstream f("atac.in");
ofstream g("atac.out");
int min(int x,int y){
return x<y?x:y;
}
void read(){
int i,u,v;
f>>N>>M>>P;
for (i=2;i<=N;++i){
f>>u>>v;
G[u].pb(mp(i,v));
G[i].pb(mp(u,v));}
f>>X>>Y>>A>>B>>C>>D;
}
bool viz[NMAX];
void euler(int vf){
vector< pair<int,int> >::iterator it;
viz[vf]=true;
v[++nr]=vf;
poz[vf]=nr;
for (it=G[vf].begin();it!=G[vf].end();++it)
if (!viz[it->ff]){
niv[it->ff]=niv[vf]+1;
s[0][it->ff]=vf;
m[0][it->ff]=it->ss;
euler(it->ff);
v[++nr]=vf;
}
}
int lca(int x,int y){
int i,j,w,k,ii,jj;
i=poz[x];
j=poz[y];
if (i>j) w=i,i=j,j=w;
w=log[j-i+1];
ii=rmq[w][i];
jj=rmq[w][j-(1<<w)+1];
if (niv[ii]<niv[jj]) k=ii;
else k=jj;
return k;
}
int drum(int x,int y){
int i,k=niv[x]-niv[y],w=1000000;
for (i=0;i<32;++i)
if ((1<<i)&k){
w=min(w,m[i][x]);
x=s[i][x];}
return w;
}
void solve(){
int i,j,x,y;
euler(1);
for (i=2;i<=nr;++i) log[i]=log[i>>1]+1;
for (i=1;i<=nr;++i) rmq[0][i]=v[i];
for (i=1;i<=log[nr];++i)
for (j=1;j<=nr-(1<<i)+1;++j){
x=rmq[i-1][j];
y=rmq[i-1][j+(1<<(i-1))];
if (niv[x]<niv[y]) rmq[i][j]=x;
else rmq[i][j]=y;
}
for (i=1;i<32;++i)
for (j=1;j<=N;++j){
s[i][j]=s[i-1][s[i-1][j]];
m[i][j]=min(m[i-1][j],m[i-1][s[i-1][j]]);
}
for (i=1;i<=M;++i){
if (X==Y) Z=0;
else{
j=lca(X,Y);
Z=min(drum(X,j),drum(Y,j));
}
x=1+(X*A+Y*B)%N;
y=1+(Y*C+Z*D)%N;
X=x;Y=y;
if (i<M-P+1) continue;
g<<Z<<'\n';}
}
int main(){
read();
solve();
return 0;
}