Pagini recente » Cod sursa (job #2172035) | Cod sursa (job #704992) | Cod sursa (job #448349) | Cod sursa (job #3188558) | Cod sursa (job #1951439)
#include <iostream>
#include <fstream>
#include <vector>
#define maxn 32000
#define mmax 500000
using namespace std;
int n,m,p,x,y,a,b,c,d,x1,y1;
int P[maxn+5][15];
int C[maxn+5][15];
int v[maxn+5][2];
int L[maxn+5];
int LCA(int p, int q)
{
if(L[p]<L[q])
{
int tmp=p;
p=q;
q=tmp;
}
int log;
for(log=1;1<<log <= L[p];log++);
log--;
for(int i=log;i>=0;i--)
if(L[p]- (1<<i)>= L[q])
p=P[p][i];
if(p==q) return p;
for(int i=log;i>=0;i--)
if(P[p][i]!=-1 && P[p][i]!=P[q][i])
p=P[p][i],q=P[q][i];
return v[p][0];
}
int caut(int up, int p, int log)
{
int poz=L[up]+(1<<log),l=p;
while(L[p]>poz )
{ if(L[P[p][log]]<poz) log--;
else p=P[p][log];
}
return p;
}
int RMQ(int p, int q)
{ if(p==q) return 0;
int up=LCA(p,q),cmin=100005;
int log=0;
if(p!=1)
{while(L[p]-(1<<(log+1))>L[up] ) log++;
cmin=min(cmin,min(C[p][log],C[ caut(up,p,log) ][log]));
}
if(q!=1)
{log=0;
while(L[q]-(1<<(log+1))>L[up] ) log++;
cmin=min(cmin,min(C[q][log],C[ caut(up,q,log) ][log]));
}
return cmin;
}
int main()
{
ifstream fin("atac.in");
ofstream fout("atac.out");
fin>>n>>m>>p;
L[1]=0;
for(int i=2;i<=n;i++)
{
int x,z;
fin>>x>>z;
v[i][0]=x;
v[i][1]=z;
L[i]=L[x]+1;
}
v[1][0]=1;
v[1][1]=0;
fin>>x>>y>>a>>b>>c>>d;
for(int i=1;i<=n;i++)
for(int j=0;1<<j<n;j++)
P[i][j]=-1;
for(int i=1;i<=n;i++)
{P[i][0]=v[i][0];
C[i][0]=v[i][1];
}
for(int j=1;(1<<j) <n;j++)
for(int i=0;i<=n;i++)
{if(P[i][j-1]!=-1)
{P[i][j]=P[ P[i][j-1] ][ j-1 ];
C[i][j]=min(C[ caut(P[i][j],i,j-1) ][j-1], C[i][j-1]);
}
}
while(m>p)
{
y1=(y*c+RMQ(x,y)*d)%n+1;
x1=(x*a+y*b)%n+1;
x=x1,y=y1;
m--;
}
for(int i=1;i<=p;i++)
{
int z=RMQ(x,y);
fout<<z<<'\n';
y1=(y*c+z*d)%n+1;
x1=(x*a+y*b)%n+1;
x=x1,y=y1;
}
fin.close();
fout.close();
return 0;
}