Pagini recente » Cod sursa (job #145172) | Cod sursa (job #3128862) | Cod sursa (job #675550) | Cod sursa (job #809509) | Cod sursa (job #2123908)
#include<iostream>
#include<fstream>
#include<vector>
#define DN 32100
#define MAXX 320100
using namespace std;
fstream fin("atac.in",ios::in), fout("atac.out",ios::out);
vector<pair<int,int> > v[DN];
int N,M,P,A,B,C,D,x,y,z;
int le,euler[2*DN],f[2*DN],l[2*DN],rmq[17][2*DN],log[2*DN];
void dfs(int nod)
{
f[nod]=le;
for(auto x:v[nod])
{
//nod->x
rmq[0][le]=x.second;
euler[++le]=x.first;
dfs(x.first);
//x->nod
rmq[0][le]=x.second;
euler[++le]=nod;
}
l[nod]=le;
rmq[0][le]=MAXX;
}
int lca(int x,int y)
{
int dif;
if(l[x]>f[y]) swap(x,y);
//minimul din intervalul l[x] f[y]
dif=f[y]-l[x];
dif=log[dif];
return min(rmq[dif][l[x]],rmq[dif][f[y]-(1<<dif)]);
}
int main()
{
int i,j,U,V,lim;
fin>>N>>M>>P;
for(i=2;i<=N;i++){
//u->i cost v
fin>>U>>V;
v[U].push_back({i,V});
}
euler[le=1]=1;
dfs(1);
for(i=1;(1<<i)<=le;i++)
{
lim=le-(1<<i);
for(j=1;j<=lim;j++)
{
rmq[i][j]=min(rmq[i-1][j], rmq[i-1][j+(1<<(i-1))]);
}
}
for(i=0;(1<<i)<2*DN;i++) log[1<<i]=i;
for(i=1;i<2*DN;i++) log[i]=max(log[i-1],log[i]);
fin>>x>>y>>A>>B>>C>>D;
for(i=1;i<=M;i++)
{
z=lca(x,y);
//cout<<i<<": "<<x<<" "<<y<<" "<<z<<"\n";
if(M-P<i)
{
fout<<z<<"\n";
}
x=(x*A + y*B)%N+1;
y=(y*C + z*D)%N+1;
}
}