Pagini recente » Cod sursa (job #1187523) | Cod sursa (job #3168297) | Cod sursa (job #1603505) | Cod sursa (job #3163494) | Cod sursa (job #760440)
Cod sursa(job #760440)
#include<fstream>
using namespace std;
int T[20][32003],rq[20][32003];
int n,a,b,c,d,m,p,x,y,nr,L[32003],z,Sol[32003];
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);
void solve();
int min(int a,int b)
{
if(a<b)
return a;
else
return b;
}
int main()
{
citire();
dfs(1);
creeaza();
solve();
}
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;
L[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;
L[p->info]=L[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]]);
}
}
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 lca(int x, int y)
{
if(L[x] < L[y])
swap(x, y);
int log1=1, log2=1;
for(; (1 << log1) < L[x]; ++log1);
for(; (1 << log2) < L[y]; ++log2);
for(int k = log1; k >= 0; --k)
if(L[x] - (1 << k) >= L[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];
}
int dist(int x, int y)
{
int sol=2147000000, lg=1;
for(; (1 << lg) < L[x]; ++lg);
for(int k = lg; k >= 0; --k)
if(L[x] - (1 << k) >= L[y])
sol = min(sol, rq[k][x]),
x = T[k][x];
return sol;
}
void solve()
{
ofstream fout("atac.out");
int z=0;
for(int i = 1; i <= m; ++i)
{
int l = lca(x, y);
if(x == y)
z = 0;
else
z = min(dist(x, l), dist(y, l));
if(i > m-p)
Sol[i-m+p] = z;
x = ((x*a + y*b) % n) + 1;
y = ((y*c + z*d) % n) + 1;
}
for(int i = 1; i <= p; ++i)
fout << Sol[i] << "\n";
}