Pagini recente » Cod sursa (job #620553) | Cod sursa (job #49346) | Cod sursa (job #520263)
Cod sursa(job #520263)
#include<fstream>
using namespace std;
int stra[20][32003],rq[20][32003];
int n,a,b,c,d,m,p,x,y,nr,nivel[32003],t[32003],z;
struct nod{
int info;
int bomb;
nod *next;};
nod *g[32003];
int maxim;
void citire();
void creeaza();
void dfs(int k);
int raspunde(int x,int y);
void adauga(int a,int b,int bombe);
int min(int a,int b)
{
if(a<b)
return a;
else
return b;
}
int main()
{
ofstream fout("atac.out");
citire();
dfs(1);
creeaza();
int i;
for(i=1;i<=m;i++)
{
if(x==y)
z=0;
else
z=raspunde(x,y);
if(i>=m-p+1)
fout<<z<<"\n";
x=(x*a+y*b)%n+1;
y=(y*c+z*d)%n+1;
}
return 0;
}
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);
t[i]=-1;
}
fin>>x>>y>>a>>b>>c>>d;
t[1]=0;
nivel[1]=1;
rq[0][1]=maxim+1;
}
void dfs(int k)
{
for(nod *p=g[k];p;p=p->next)
{
if(t[p->info]==-1)
{
t[p->info]=k;
rq[0][p->info]=p->bomb;
nivel[p->info]=nivel[k]+1;
dfs(p->info);
}
}
}
void creeaza()
{
int i,j;
for(i=1;i<=n;i++)
stra[0][i]=t[i];
int pres=1;
for(i=1;pres==1;i++)
{
pres=0;
for(j=1;j<=n;j++)
{
stra[i][j]=stra[i-1][stra[i-1][j]];
rq[i][j]=min(rq[i-1][j],rq[i-1][stra[i-1][j]]);
if(stra[i][j]>0)
pres=1;
}
}
}
int raspunde(int x,int y)
{
int sol=min(rq[0][x],rq[0][y]);
int mic,mare;
if(nivel[x]>nivel[y])
mare=x,mic=y;
else
mare=y,mic=x;
int i=0;
while(nivel[stra[i+1][mare]]>=nivel[mic])
{
i++;
if(rq[i][mare]<sol && rq[i][mare]>0)
sol=rq[i][mic];
}
mare=stra[i][mare];
while(nivel[t[mare]]>=nivel[mic])
{
if(rq[0][mare]<sol && rq[0][mare]>0)
sol=rq[0][mare];
mare=t[mare];
}
i=0;
int pres=0;
while(pres==0)
{
if(stra[i+1][mare]!=stra[i+1][mic])
i++;
else
pres=1;
if(rq[i][mare]<sol && rq[i][mare]>0)
sol=rq[i][mare];
if(rq[i][mic]<sol && rq[i][mic]>0)
sol=rq[i][mic];
}
mare=stra[i][mare],mic=stra[i][mic];
pres=0;
if(mare!=mic)
{
while(pres==0)
{
if(rq[0][mare]<sol && rq[0][mare]>0)
sol=rq[0][mare];
if(rq[0][mic]<sol && rq[0][mic]>0)
sol=rq[0][mic];
if(mare==mic)
pres=1;
mare=t[mare];
mic=t[mic];
}
}
return sol;
}
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;
}