Pagini recente » Cod sursa (job #593358) | Cod sursa (job #1993060) | Cod sursa (job #1862836) | Cod sursa (job #3209709) | Cod sursa (job #568535)
Cod sursa(job #568535)
#include <fstream>
#include <vector>
using namespace std;
const char InFile[]="atac.in";
const char OutFile[]="atac.out";
const int MaxN=1<<15;
const int MaxM=1<<19;
const int LogMaxN=16;
const int INF=1<<30;
ifstream fin(InFile);
ofstream fout(OutFile);
struct s_edge
{
s_edge(int _y=0, int _w=0):y(_y),w(_w){}
int y,w;
};
int N,M,P,u,v,k,X,Y,A,B,C,D,Q[MaxM],niv[MaxN],T[LogMaxN][MaxN],W[LogMaxN][MaxN],lg[MaxN],viz[MaxN];
vector<s_edge> G[MaxN];
void DFS(int nod, int t)
{
if(viz[nod])
{
return;
}
niv[nod]=k;
++k;
viz[nod]=1;
T[0][nod]=t;
for(vector<s_edge>::iterator it=G[nod].begin();it!=G[nod].end();++it)
{
if(t!=it->y)
{
DFS(it->y,nod);
}
else
{
W[0][nod]=it->w;
}
}
--k;
}
inline void preprocesare()
{
W[0][1]=INF;
for(register int i=2;i<=N;++i)
{
lg[i]=lg[i>>1]+1;
}
for(register int i=1;i<LogMaxN;++i)
{
for(register int j=1;j<=N;++j)
{
T[i][j]=T[i-1][T[i-1][j]];
W[i][j]=min(W[i-1][j],W[i-1][T[i-1][j]]);
}
}
}
inline int query(int x,int y)
{
if(x==y)
{
return 0;
}
int w=INF;
if(niv[x]<niv[y])
{
swap(x,y);
}
while(niv[x]!=niv[y])
{
int k=lg[niv[x]-niv[y]];
w=min(w,W[k][x]);
x=T[k][x];
}
int k=LogMaxN-1;
while(x!=y)
{
while(k>0 && T[k][x]==T[k][y])
{
k/=2;
}
/*if(k==-1)
{
w=min(w,W[0][x]);
w=min(w,W[0][y]);
break;
}*/
w=min(w,W[k][x]);
w=min(w,W[k][y]);
x=T[k][x];
y=T[k][y];
}
return w;
}
int main()
{
fin>>N>>M>>P;
for(register int i=2;i<=N;++i)
{
fin>>u>>v;
G[i].push_back(s_edge(u,v));
G[u].push_back(s_edge(i,v));
}
fin>>X>>Y>>A>>B>>C>>D;
fin.close();
DFS(1,0);
preprocesare();
for(register int i=1;i<=M;++i)
{
int Z=query(X,Y);
Q[++Q[0]]=Z;
int Xprim=(X*A+Y*B)%N+1;
int Yprim=(Y*C+Z*D)%N+1;
X=Xprim;
Y=Yprim;
}
for(register int i=Q[0]-P+1;i<=Q[0];++i)
{
fout<<Q[i]<<"\n";
}
fout.close();
return 0;
}