Pagini recente » Cod sursa (job #2062089) | Cod sursa (job #2348315) | Cod sursa (job #619179) | Cod sursa (job #821111) | Cod sursa (job #2974191)
#include <fstream>
#include<vector>
#include<climits>
#define NMAX 32001
#define INF INT_MAX
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
int n,m,x,y,A,B,C,D,X,Y,p;
vector<int>v[NMAX];
int stramos[30][NMAX],cost[30][NMAX],nivel[NMAX],start[NMAX],finish[NMAX],k;
void dfs(int nod,int niv)
{
nivel[nod]=niv;
k++;
start[nod]=k;
for(int i=0;i<v[nod].size();i++)
{
int nod1=v[nod][i];
dfs(nod1,niv+1);
}
finish[nod]=++k;
}
bool str(int x,int y)
{
return start[x]<=start[y]&&finish[y]<=finish[x];
}
void calcul_stramosi()
{
for(int i=1;(1<<i)<=n;i++)
for(int j=1;j<=n;j++)
{
cost[i][j]=min(cost[i-1][j],cost[i-1][stramos[i-1][j]]);
stramos[i][j]=stramos[i-1][stramos[i-1][j]];
}
}
int lca(int x,int y)
{
if(str(x,y))
return x;
if(str(y,x))
return y;
for(int p=16;p>=0;p--)
{
int z=stramos[p][x];
if(z&&!str(z,y))
x=z;
}
return stramos[0][x];
}
int costuri(int x,int y)
{
if(x==y)
return 0;
int LCA= lca(x,y);
int minn=INF;
for (int nod:{x,y})
{
int diff=nivel[nod]-nivel[LCA];
for (int p=16;p>=0;p--)
{
if (diff>=(1<<p))
{
diff-=(1<<p);
minn=min(minn,cost[p][nod]);
nod=stramos[p][nod];
}
}
}
return minn;
}
int main()
{
fin>>n>>m>>p;
for(int i=2;i<=n;i++)
{
fin>>stramos[0][i]>>cost[0][i];
v[stramos[0][i]].push_back(i);
}
dfs(1,1);
calcul_stramosi();
fin>>X>>Y>>A>>B>>C>>D;
for(int i=1;i<=m;i++)
{
int sol=costuri(X,Y);
if(m-i+1<=p)
fout<<sol<<"\n";
X=(X*A+Y*B)%n+1;
Y=(Y*C+sol*D)%n+1;
}
return 0;
}