Pagini recente » Cod sursa (job #7575) | Cod sursa (job #63263) | Cod sursa (job #1264713) | Cod sursa (job #1014524) | Cod sursa (job #912799)
Cod sursa(job #912799)
#include <fstream>
#include <vector>
using namespace std;
struct edge{
int to,cost;
};
#define maxn 32005
#define pb push_back
#define forEach(G) for( typeof(G.begin()) it = G.begin() ; it != G.end() ; ++ it )
vector<edge> G[maxn];
ifstream in("atac.in");
ofstream out("atac.out");
int n,m,p;
int RMQ[17][maxn*2];
int ancestor[17][maxn];
int dest[17][maxn];
int first[maxn];
int root[maxn];
int cost[maxn];
int eul[maxn*2],H[maxn*2];
int CR;
int lg[maxn*2];
bool viz[maxn];
void dfs(const int &nod,const int &lev)
{
viz[nod]=1;
eul[++CR] = nod;
first[nod]=CR;
H[CR]=lev;
forEach(G[nod]){
if(!viz[it->to]){
dfs(it->to,lev+1);
root[it->to]=nod;
cost[it->to]=it->cost;
}
eul[++CR]=nod;
H[CR]=lev;
}
}
void build_RMQ()
{
int i,j,l;
for(i=2;i<=CR;++i)
lg[i] = lg[i/2]+1;
for(i=1;i<=CR;++i)
RMQ[0][i]=i;
for(i=1;(1 << i) < CR;++i){
for(j=1; j <= CR - (1 << i); ++ j ){
l = 1 << (i-1);
RMQ[i][j] = RMQ[i-1][j];
if(H[RMQ[i-1][j+l]] < H[RMQ[i][j]])
RMQ[i][j] = RMQ[i-1][j+l];
}
}
}
int LCA(int x,int y)
{
x = first[x],y = first[y];
if(x > y)
swap(x,y);
int diff = y-x+1,l = lg[diff],sol;
sol = RMQ[l][x];
diff -= 1 << l;
if(H[RMQ[l][x+diff]] < H[sol])
sol = RMQ[l][x+diff];
return sol;
}
void precalc()
{
int i,j;
for(i=1;i<=n;++i){
ancestor[0][i] = root[i];
dest[0][i] = cost[i];
}
for(i=1;(1<<i)<=n;++i){
for(j=1;j<=n;++j){
ancestor[i][j] = ancestor[i-1][ancestor[i-1][j]];
dest[i][j] = min(dest[i-1][j],dest[i-1][ancestor[i-1][j]]);
}
}
}
int query(int nod,int cat){
int ret = 1 << 30;
for(int i = 0 ; cat; ++i){
if(cat & (1 << i)){
ret = min(ret,dest[i][nod]);
nod = ancestor[i][nod];
cat ^= 1 << i;
}
}return ret;
}
int solve(int a,int b)
{
if(a==b)return 0;
int mid = LCA(a,b),Ha,Hb;
Ha = H[first[a]] - H[mid];
Hb = H[first[b]] - H[mid];
return min(query(a,Ha),query(b,Hb));
return 1;
}
int main()
{
int i,a,b;
int X,Y,A,B,C,D;
in >> n >> m >> p;
for(i=2;i<=n;++i){
in >> a >> b;
G[i].pb({a,b});
G[a].pb({i,b});
}in >> X >> Y >> A >> B >> C >> D;
dfs(1,1);
build_RMQ();
precalc();
int val;
for(i=1;i<=m;++i){
val = solve(X,Y);
X = ( X*A + Y*B )%n + 1;
Y = ( Y*C + val*D )%n + 1;
if(m-i < p)
out << val << "\n";
}
return 0;
}