Pagini recente » Cod sursa (job #2461043) | Cod sursa (job #3041680) | Cod sursa (job #1282135) | Cod sursa (job #872034) | Cod sursa (job #420021)
Cod sursa(job #420021)
#include <fstream>
#include <vector>
using namespace std;
#define NMAX 32004
#define oo 100000
bool sch;
ofstream fout("atac.out");
int S[15][NMAX],Ct[15][NMAX];
int Niv[NMAX];
int N,M,P,X,Y,A,B,C,D,nx,ny;
vector < pair<int,int> > Ad[NMAX];
void citire()
{
ifstream fin("atac.in");
fin>>N>>M>>P;
int i;
for (i=2;i<=N;++i)
{ int x,c;
fin>>x>>c;
Ad[i].push_back( make_pair(x,c) );
Ad[x].push_back( make_pair(i,c) );
}
fin>>X>>Y>>A>>B>>C>>D;
fin.close();
}
void dfs(int x, int nv)
{
Niv[x]=nv;
for (int i=0;i<Ad[x].size();++i)
if (Ad[x][i].first!=S[0][x])
{
S[0][Ad[x][i].first]=x; Ct[0][Ad[x][i].first]=Ad[x][i].second;
dfs(Ad[x][i].first,nv+1);
}
}
void LCA(int x, int y)
{ sch=0;
if (Niv[x]<Niv[y]) { int aux=x; x=y; y=aux; sch=1;}
int logx,logy;
for (logx=0;(1<<logx)<Niv[x];++logx) ;
for (logy=0;(1<<logy)<Niv[y];++logy) ;
nx=ny=0; int k;
for (k=logx;k>=0;--k)
if (Niv[x]-(1<<k)>=Niv[y]) {x=S[k][x]; nx+=(1<<k);}
if (x==y) return ;
for (k=logy; k>=0; --k)
if (S[k][x] && S[k][x]!=S[k][y])
{
x=S[k][x]; nx+=(1<<k);
y=S[k][y]; ny+=(1<<k);
}
nx++; ny++;
return ;
}
void nextpair(int &X, int &Y, int Z)
{ int X2;
X2 = (X*A + Y*B) % N + 1;
Y = (Y*C + Z*D) % N + 1;
X=X2;
}
int dist(int x, int nx)
{
int cmin=oo, k;
k=0;
while (nx>=(1<<k)) ++k;
--k;
while (k>=0)
{
if ((1<<k)&nx)
{
cmin=min(cmin,Ct[k][x]);
x=S[k][x];
}
--k;
}
return cmin;
}
int main()
{
citire();
dfs(1,0);
int k,i;
for (k=1;(1<<k)<=N;++k)
for (i=1;i<=N;++i)
{ S[k][i]=S[k-1][S[k-1][i]];
Ct[k][i]=min(Ct[k-1][S[k-1][i]],Ct[k-1][i]);
}
for (int test=1;test<=M;++test)
{
if (X==Y) {
if (test>M-P+1) fout<<"0\n";
nextpair(X,Y,0);
continue;
}
LCA(X,Y);
if (sch) { int aux=nx; nx=ny; ny=aux;}
int Z=min(dist(X,nx),dist(Y,ny));
if (test>=M-P+1) fout<<Z<<"\n";
nextpair(X,Y,Z);
}
return 0;
}