Pagini recente » Cod sursa (job #1700058) | Cod sursa (job #924873) | Cod sursa (job #474303) | Cod sursa (job #1687669) | Cod sursa (job #519762)
Cod sursa(job #519762)
#include<fstream>
#include<cmath>
using namespace std;
int euler[300000],rq[32004],nivel[32004],eulercost[300000],lun;
struct nod{
int info;
int bomb;
nod *next;
};
nod *g[32003];
int n,x,z,y,p,m,a,b,c,d,nreuler,vizitat[32000],aparitii[32000],maxim,t[32004],nr;
void citire();
void dfs(int k);
void adauga(int a,int b,int bombe);
void impartire();
int rmq(int poz1,int poz2);
int main()
{
int i;
ofstream fout("atac.out");
citire();
dfs(1);
nr--;
impartire();
for(i=1;i<=m;i++)
{
if(aparitii[x]<aparitii[y])
z=rmq(aparitii[x],aparitii[y]);
else
z=rmq(aparitii[y],aparitii[x]);
if(m-i+1<=p)
fout<<z<<"\n";
x=(x*a+y*b)%n+1;
y=(y*c+z*d)%n+1;
}
}
void citire()
{
ifstream fin("atac.in");
fin>>n>>m>>p;
int i;
for(i=2;i<=n;i++)
{
int nodu,bombe;
fin>>nodu>>bombe;
if(bombe>maxim)
maxim=bombe;
adauga(i,nodu,bombe);
adauga(nodu,i,bombe);
}
fin>>x>>y>>a>>b>>c>>d;
euler[++nr]=1;
nivel[0]=1;
eulercost[1]=maxim+1;
aparitii[1]=1;
}
void dfs(int k)
{
vizitat[k]=1;
nivel[k]=nivel[t[k]]+1;
for(nod *p=g[k];p;p=p->next)
if(vizitat[p->info]==0)
{
euler[++nr]=p->info;
aparitii[p->info]=nr;
eulercost[nr]=p->bomb;
t[p->info]=k;
dfs(p->info);
}
euler[++nr]=t[k];
eulercost[nr]=maxim+1;
}
void adauga(int a,int b,int bombe)
{
nod *p=new nod;
p->info=b;
p->bomb=bombe;
p->next=g[a];
g[a]=p;
}
void impartire()
{
lun=sqrt(nr);
int i;
for(i=1;i<=nr;i++)
{
int parte=i/lun;
if(i%lun>0)
parte++;
if(rq[parte]==0)
rq[parte]=eulercost[i];
else
if(eulercost[i]<rq[parte])
rq[parte]=eulercost[i];
}
}
int rmq(int poz1,int poz2)
{
int inceput=poz1/lun+1;
int sf=poz2/lun;
int minim=maxim+2;
int i;
for(i=poz1;i<=inceput*lun;i++)
if(eulercost[i]<minim)
minim=eulercost[i];
for(i=inceput;i<=sf;i++)
if(rq[i]<minim)
minim=rq[i];
for(i=sf*lun;i<=poz2;i++)
if(eulercost[i]<minim)
minim=eulercost[i];
return minim;
}