Pagini recente » Cod sursa (job #926313) | Cod sursa (job #2407268) | Cod sursa (job #1744101) | Cod sursa (job #938034) | Cod sursa (job #3241733)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("atac.in");
ofstream fout ("atac.out");
int t[15][32001],val[15][32001],nivel[32001];
int x,y,a,b,c,d,n,i,nivx,nivy,cost,m,p,pp,z,dif;
vector <pair <int,int>> v[32001];
void dfs (int nod,int tt,int cost,int niv)
{
t[0][nod]=tt;
val[0][nod]=cost;
nivel[nod]=niv;
for (int i=0; i<v[nod].size (); i++)
{
int vecin=v[nod][i].first;
if (vecin!=tt)
dfs (vecin,nod,v[nod][i].second,niv+1);
}
}
int lca (int x,int y)
{
nivx=nivel[x];
nivy=nivel[y];
if (nivx<nivy)
{
swap (x,y);
swap (nivx,nivy);
}
cost=100001;
dif=nivx-nivy;
for (p=14; p>=0; p--)
{
if ((dif>>p)&1)
{
cost=min (cost,val[p][x]);
x=t[p][x];
}
}
if (x==y)
return cost;
for (p=14; p>=0; p--)
{
if (t[p][x]!=t[p][y])
{
cost=min (cost,min (val[p][x],val[p][y]));
x=t[p][x];
y=t[p][y];
}
}
cost=min (cost,min (val[0][x],val[0][y]));
return cost;
}
int main()
{
fin>>n>>m>>pp;
for (i=2; i<=n; i++)
{
fin>>x>>c;
v[x].push_back (make_pair (i,c));
v[i].push_back (make_pair (x,c));
}
dfs (1,0,0,1);
for (p=1; p<=14; p++)
{
for (i=1; i<=n; i++)
{
val[p][i]=min (val[p-1][i],val[p-1][t[p-1][i]]);
t[p][i]=t[p-1][t[p-1][i]];
}
}
fin>>x>>y>>a>>b>>c>>d;
for (i=1; i<=m; i++)
{
z=lca (x,y);
if (i>=m-pp+1)
fout<<z<<"\n";
x=(1ll*x*a+1ll*y*b)%n+1;
y=(1ll*y*c+1ll*z*d)%n+1;
}
return 0;
}