Pagini recente » Istoria paginii runda/chuck_norris | Cod sursa (job #1519159) | Istoria paginii runda/simulare_oni1234 | Cod sursa (job #2095931) | Cod sursa (job #1129567)
#include<fstream>
#include<vector>
#include<algorithm>
#define NMAX 32005
#define MMAX
#define L depth.size()-1
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
int n,m,p,k,X,Y,a,b,c,d,v[NMAX];
short euler[2*NMAX],lca_rmq[16][2*NMAX],first[NMAX],level[2*NMAX],Log[2*NMAX],mins[16][NMAX],Lev[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(short nod,short niv)
{
if(depth.empty())
depth.push_back((1<<30));
else
depth.push_back(min(v[nod],depth[L]));
euler[++k]=nod;
first[nod]=k;
level[k]=niv;
Lev[nod]=niv;
for(size_t i=0;i<G[nod].size();i++)
{
DFS(G[nod][i],niv+1);
euler[++k]=nod;
level[k]=niv;
}
for(size_t i=0;(1U<<i)<=depth.size();i++)
mins[i][nod]=depth[L+1-(1<<i)];
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];
}
short query_lca(short x,short 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);
lca_rmq_build();
for(;m;m--)
{
short LCA=query_lca(first[X],first[Y]),Z=(1<<15)-1;
for(int i=Lev[X]-Lev[LCA];i;i-=(1<<Log[i]))
Z=min(Z,mins[Log[i]][X]);
for(int i=Lev[Y]-Lev[LCA];i;i-=(1<<Log[i]))
Z=min(Z,mins[Log[i]][Y]);
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;
}