Pagini recente » Cod sursa (job #1571715) | Cod sursa (job #1839007) | Cod sursa (job #791276) | Cod sursa (job #3151692) | Cod sursa (job #215631)
Cod sursa(job #215631)
#include<stdio.h>
#define N 1<<15
#define L 15
#define MAX 100005
int n,m,p,tata[N],cost[N],stra[N][L],bom[N][L],nivel[N],a,b,c,d,x,y;
void citire()
{
scanf("%d%d%d",&n,&m,&p);
for(int i=2;i<=n;++i)
{
scanf("%d%d",&tata[i],&cost[i]);
nivel[i]=1+nivel[tata[i]];
}
scanf("%d%d%d%d%d%d",&x,&y,&a,&b,&c,&d);
}
inline int minim(int a,int b)
{
return a < b ? a : b;
}
void stramosi()//completeaza stra[i][j]=stramosul de 2^j al lui i si bom[i][j] costul min pt a distruge dr de la i la stra[i][j]
{
for(int i=1;i<=n;++i)
{
stra[i][0]=tata[i];
bom[i][0]=cost[i];
}
for(int i=1;i<=n;++i)
for(int j=1;j<L;++j)
if(stra[i][j-1] && stra[stra[i][j-1]][j-1])
{
stra[i][j]=stra[stra[i][j-1]][j-1];
bom[i][j]=minim(bom[i][j-1],bom[stra[i][j-1]][j-1]);
}
}
inline void schimb(int &a,int &b)
{
int aux=a;
a=b;
b=aux;
}
int lca(int p,int q)
{
if(nivel[p]<nivel[q])
schimb(p,q);
int log=1,min=MAX;
while((1<<log)<=nivel[p])//calculez log=[log(nivel[p])]
++log;
--log;
//il aduc pe p pe acelasi nivel cu q
for(int j=log; j>=0 && nivel[p]!=nivel[q] ; --j)
if(nivel[p]-(1<<j)>=nivel[q])
{
min=minim(min,bom[p][j]);
p=stra[p][j];
}
if(p==q)
return min;
//gasesc lca pt p si q
for(int j=log ; j>=0 ; --j)
if(nivel[p]>=(1<<j) && stra[p][j]!=stra[q][j])
{
min=minim(min,bom[p][j]);
p=stra[p][j];
min=minim(min,bom[q][j]);
q=stra[q][j];
}
min=minim(min,bom[p][0]);
min=minim(min,bom[q][0]);
return min;
}
void calcul()
{
int z;
for(int i=1;i<=m;++i)
{
z=lca(x,y);
if(i+p-1>=m)
printf("%d\n",z);
x = (x*a + y*b) % n + 1;
y = (y*c + z*d) % n + 1;
}
}
int main()
{
freopen("atac.in","r",stdin);
freopen("atac.out","w",stdout);
citire();
stramosi();
//proba(stra);
//proba(bom);
calcul();
return 0;
}