Pagini recente » Cod sursa (job #610555) | Cod sursa (job #384318) | Cod sursa (job #3185493) | Cod sursa (job #425332) | Cod sursa (job #520287)
Cod sursa(job #520287)
#include<fstream>
using namespace std;
int t[20][32003],rq[20][32003];
int n,a,b,c,d,m,p,x,y,nr,nivel[32003],z;
struct nod{
int info;
int bomb;
nod *next;};
nod *g[32003];
int maxim;
void citire();
void creeaza();
void dfs(int k);
int lca(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 dist(int x,int y);
int main()
{
ofstream fout("atac.out");
citire();
dfs(1);
creeaza();
int i;
for(i=1;i<=m;i++)
{
if(x==y)
z=0;
else
{
int stra=lca(x,y);
z=min(dist(x,stra),dist(y,stra));
}
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[0][i]=-1;
}
fin>>x>>y>>a>>b>>c>>d;
t[0][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[0][p->info]==-1)
{
t[0][p->info]=k;
rq[0][p->info]=p->bomb;
nivel[p->info]=nivel[k]+1;
dfs(p->info);
}
}
}
void creeaza()
{
for(int k=1;(1<<k)<n;k++)
for(int i=1;i<=n;i++)
{
t[k][i]=t[k-1][t[k-1][i]];
rq[k][i]=min(rq[k-1][i],rq[k-1][t[k-1][i]]);
}
}
int lca(int x,int y)
{
int aux;
if(nivel[x]<nivel[y])
{
aux=x;
x=y;
y=x;
}
int log1=0,log2=0;
for(;(1<<log1)<nivel[x];log1++);
for(;(1<<log2)<nivel[y];log2++);
for(int k=log1;k>=0;k--)
if(nivel[x]-(1>>k)>=nivel[y])
x=t[k][x];
if(x==y)
return x;
for(int k=log2;k>=0;k--)
if(t[k][x]!=t[k][y])
{
x=t[k][x];
y=t[k][y];
}
return t[0][x];
}
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;
}
int dist(int x,int y)
{
int sol=2147000000;
int log1=1;
for(;(1<<log1)<nivel[x];log1++)
for(int k=log1;k>=0;k--)
if(nivel[x]-(1>>k)>nivel[y])
{
if(rq[k][x]<sol)
sol=rq[k][x];
x=t[k][x];
}
return sol;
}