Pagini recente » Istoria paginii runda/tgesgt | Cod sursa (job #2000194) | Istoria paginii runda/00998 | Cod sursa (job #2698944) | Cod sursa (job #1129670)
#include<fstream>
#include<vector>
#include<algorithm>
#define NMAX 32005
#define MMAX
#define L depth.size()
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
int n,m,p,k,X,Y,a,b,c,d,v[NMAX],mins[17][NMAX],first[NMAX];
int euler[2*NMAX],lca_rmq[17][2*NMAX],level[2*NMAX],Log[2*NMAX],Lev[NMAX],TT[17][NMAX];
vector<int> G[NMAX],depth,sol;
void read()
{
fin>>n>>m>>p;
for(int i=2,x;i<=n;i++)
{
fin>>x>>v[i];
G[x].push_back(i);
}
fin>>X>>Y>>a>>b>>c>>d;
}
void DFS(int nod,int niv,int tt)
{
depth.push_back(nod);
euler[++k]=nod;
first[nod]=k;
level[k]=niv;
Lev[nod]=niv;
mins[0][nod]=v[nod];
TT[0][nod]=tt;
for(size_t i=1;(1U<<i)<depth.size();i++)
{
mins[i][nod]=min(mins[i-1][nod],mins[i-1][depth[L-1-(1<<(i-1))]]);
TT[i][nod]=TT[i-1][depth[L-1-(1<<(i-1))]];
}
for(size_t i=0;i<G[nod].size();i++)
{
DFS(G[nod][i],niv+1,nod);
euler[++k]=nod;
level[k]=niv;
}
depth.pop_back();
}
void lca_rmq_build()
{
for(int i=2;i<=k;i++)
Log[i]=Log[i/2]+1;
for(int i=1;i<=k;i++)
lca_rmq[0][i]=i;
for(int i=1,p=(1<<i);p<k;i++,p<<=1)
for(int j=1;j<=k-p;j++)
if(level[lca_rmq[i-1][j+p/2]]<level[lca_rmq[i-1][j]])
lca_rmq[i][j]=lca_rmq[i-1][j+p/2];
else
lca_rmq[i][j]=lca_rmq[i-1][j];
}
int query_lca(int x,int y)
{
if(x>y)
swap(x,y);
int dif=y-x+1,line=Log[dif],plus=dif-(1<<line);
if(level[lca_rmq[line][x+plus]]<level[lca_rmq[line][x]])
return euler[lca_rmq[line][x+plus]];
return euler[lca_rmq[line][x]];
}
int main()
{
read();
DFS(1,0,0);
lca_rmq_build();
for(;m;m--)
{
int LCA=query_lca(first[X],first[Y]),Z=(1<<30),x=X,y=Y;
for(int i=Lev[X]-Lev[LCA];i;i-=(1<<Log[i]))
{
Z=min(Z,mins[Log[i]][X]);
X=TT[Log[i]][X];
}
for(int i=Lev[Y]-Lev[LCA];i;i-=(1<<Log[i]))
{
Z=min(Z,mins[Log[i]][Y]);
Y=TT[Log[i]][Y];
}
/*for(int i=X;i!=LCA;i=TT[0][i])
Z=min(Z,v[i]);
for(int i=Y;i!=LCA;i=TT[0][i])
Z=min(Z,v[i]);*/
if(x==y)
Z=0;
X=(x*a+y*b)%n+1;
Y=(y*c+Z*d)%n+1;
sol.push_back(Z);
}
for(size_t i=sol.size()-p;i<sol.size();i++)
fout<<sol[i]<<'\n';
return 0;
}