Pagini recente » Cod sursa (job #43588) | Cod sursa (job #369313) | Cod sursa (job #252296) | Cod sursa (job #1824214) | Cod sursa (job #382977)
Cod sursa(job #382977)
#include<fstream>
#include<vector>
using namespace std;
const char iname[]="atac.in";
const char oname[]="atac.out";
const int maxn=33000;
const int maxl=16;
const int INF=(1<<31)-1;
ifstream f(iname);
ofstream g(oname);
//distanta lca
struct dis
{
int w;
int dis;
} anc[maxl][maxn];
int log[maxn*2];
//variabile normale
int i,j,n,m,a,b,c,d,p,x,y,z;
//rmq
int sons[maxn],height[maxn],euler[maxn*2],rmq[maxl*2][maxn*2],k;
int pos[maxn];
vector<int> E[maxn];
void get_height(int x)
{
if(height[x])
return;
if(anc[0][x].w==0)
{
height[x]=1;
return;
}
if(height[anc[0][x].w]==0)
get_height(anc[0][x].w);
height[x]=height[anc[0][x].w]+1;
}
void build_euler(int x)
{
euler[++k]=x;
for(vector<int>::iterator it=E[x].begin();it!=E[x].end();++it)
build_euler(*it),euler[++k]=x;
pos[x]=k;
}
int lca(int x,int y)
{
int aux;
if(x>y)
aux=x,x=y,y=aux;
int dis=y-x+1;
int r=rmq[log[dis]][y-(1<<log[dis])+1];
if(height[rmq[log[dis]][x]]<height[r])
r=rmq[log[dis]][x];
return r;
}
int dis(int x,int y)
{
int dis=height[x]-height[y];
int step,rez=x,ans=INF;
for(step=0;(1<<step)<=dis;++step)
if((1<<step)&dis)
ans=min(ans,anc[step][rez].dis),rez=anc[step][rez].w;
if(ans==INF)
ans=0;
return ans;
}
int main()
{
f>>n>>m>>p;
for(i=2;i<=n;++i)
f>>anc[0][i].w>>anc[0][i].dis,++sons[anc[0][i].w],E[anc[0][i].w].push_back(i);
for(i=2;i<=n+n;++i)
log[i]=log[i>>1]+1;
for(i=1;i<=log[n];++i)
for(j=n;j;--j)
anc[i][j].w=anc[i-1][anc[i-1][j].w].w,anc[i][j].dis=min(anc[i-1][j].dis,anc[i-1][anc[i-1][j].w].dis);
for(i=1;i<=n;++i)
get_height(i);
build_euler(1);
for(i=1;i<=k;++i)
rmq[0][i]=i;
for(i=1;i<=log[k];++i)
for(j=k-(1<<i)+1;j;--j)
{
rmq[i][j]=rmq[i-1][j];
if(height[euler[rmq[i-1][j+(1<<i-1)]]]<height[euler[rmq[i-1][j]]])
rmq[i][j]=rmq[i-1][j+(1<<i-1)];
}
m-=p;
f>>x>>y>>a>>b>>c>>d;
for(i=1;i<=m;++i)
{
z=euler[lca(pos[x],pos[y])];
z=min(dis(x,z),dis(y,z));
x=(x*a+y*b)%n+1;
y=(y*c+z*d)%n+1;
}
for(i=1;i<=p;++i)
{
z=euler[lca(pos[x],pos[y])];
z=min(dis(x,z),dis(y,z));
x=(x*a+y*b)%n+1;
y=(y*c+z*d)%n+1;
g<<z<<"\n";
}
f.close();
g.close();
return 0;
}