Pagini recente » Cod sursa (job #1202780) | Cod sursa (job #1511980) | Cod sursa (job #2780088) | Cod sursa (job #2580547) | Cod sursa (job #2632199)
#include <bits/stdc++.h>
#define DIM 35000
#define DIMM 500010
#define INF 2000000000
using namespace std;
int E[DIM*4],p[DIM*4],first[DIM],val[DIM],ans[DIMM],level[DIM];
int nr_chains,n,m,P,i,j,x,y,sol,k,cost,a,b,c,d;
int stramos[22][DIM],dp[22][DIM];
pair <int,int> rmq[22][DIM*4];
vector <pair<int,int> > L[DIM];
void dfs (int nod, int tata){
level[nod] = 1 + level[tata];
E[++k] = nod;
first[nod] = k;
for (auto it : L[nod]){
int vecin = it.first, cost = it.second;
if (vecin != tata){
stramos[0][vecin] = nod;
dp[0][vecin] = cost;
dfs (vecin,nod);
E[++k] = nod;
}}}
int get_lca (int x, int y){
int posx = first[x], posy = first[y];
if (posx > posy)
swap (posx,posy);
int nr = p[posy - posx + 1];
pair <int, int> sol = min (rmq[nr][posx], rmq[nr][posy - (1<<nr) + 1]);
return E[sol.second];
}
void query (int x, int y){
int lca = get_lca (x,y);
for (int i=20;i>=0;i--){
int nod = stramos[i][x];
if (level[nod] >= level[lca]){
sol = min (sol,dp[i][x]);
x = nod;
}}
for (int i=20;i>=0;i--){
int nod = stramos[i][y];
if (level[nod] >= level[lca]){
sol = min (sol,dp[i][y]);
y = nod;
}}}
int main (){
ifstream fin ("atac.in");
ofstream fout ("atac.out");
fin>>n>>m>>P;
for (i=2;i<=n;i++){
fin>>x>>cost;
L[i].push_back(make_pair(x,cost));
L[x].push_back(make_pair(i,cost));
}
dfs (1,0);
for (i=1;i<=k;i++)
rmq[0][i] = make_pair(level[E[i]],i);
for (i=1;(1<<i)<=k;i++)
for (j=1;j<=k;j++){
rmq[i][j] = rmq[i-1][j];
if (j + (1<<(i-1)) <= k && rmq[i-1][j + (1<<(i-1))].first < rmq[i][j].first)
rmq[i][j] = rmq[i-1][j + (1<<(i-1))];
}
for (i=2;i<=k;i++)
p[i] = p[i/2] + 1;
for (i=1;(1<<i)<=n;i++){
for (j=1;j<=n;j++){
stramos[i][j] = stramos[i-1][stramos[i-1][j]];
dp[i][j] = min (dp[i-1][j],dp[i-1][stramos[i-1][j]]);
}
}
fin>>x>>y>>a>>b>>c>>d;
sol = INF;
query (x,y);
if (x == y)
sol = 0;
ans[1] = sol;
for (i=2;i<=m;i++){
x = (x * a + y * b) % n + 1;
y = (y * c + sol * d) % n + 1;
sol = INF;
query (x,y);
if (x == y)
sol = 0;
ans[i] = sol;
}
for (i=m-P+1;i<=m;i++)
fout<<ans[i]<<"\n";
return 0;
}