Pagini recente » Cod sursa (job #2476073) | Cod sursa (job #786082) | Cod sursa (job #3295967) | Cod sursa (job #2066089) | Cod sursa (job #2079825)
# include <fstream>
# include <vector>
# define DIM 32010
# define INF 1000000000
# define f first
# define s second
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
vector<pair<int,int> > Lista[DIM];
int t[17][DIM],D[17][DIM],niv[DIM];
int n,m,p,i,j,step,x,y,cost,a,b,c,d,xi,yi,val;
void dfs(int nc){
for(int i=0;i<Lista[nc].size();i++){
int nv=Lista[nc][i].f;
int cost=Lista[nc][i].s;
if(!niv[nv]){
niv[nv]=niv[nc]+1;
D[0][nv]=cost;
t[0][nv]=nc;
dfs(nv);
}
}
}
int main () {
fin>>n>>m>>p;
for(i=2;i<=n;i++){
fin>>y>>cost;
x=i;
Lista[x].push_back(make_pair(y,cost));
Lista[y].push_back(make_pair(x,cost));
}
niv[1]=1;
dfs(1);
for(j=1,step=2;step<=n;step*=2,j++)
for(i=1;i<=n;i++){
t[j][i]=t[j-1][t[j-1][i]];
D[j][i]=min(D[j-1][i],D[j-1][t[j-1][i]]);
}
fin>>x>>y>>a>>b>>c>>d;
for(i=m;i>=1;i--){
xi=x;
yi=y;
if(x==y){
val=0;
if(i<=p)
fout<<val<<"\n";
x=xi;
y=yi;
x=(x*a+y*b)%n+1;
y=(y*c+val*d)%n+1;
continue;
}
if(niv[x]<niv[y])
swap(x,y);
val=INF;
for(step=1,j=0;step<=n;step*=2,j++);
for(;step;step/=2,j--)
if(niv[x]-step>=niv[y]){
val=min(val,D[j][x]);
x=t[j][x];
}
if(x==y){
if(i<=p)
fout<<val<<"\n";
x=xi;
y=yi;
x=(x*a+y*b)%n+1;
y=(y*c+val*d)%n+1;
continue;
}
for(step=1,j=0;step<=n;step*=2,j++);
for(;step;step/=2,j--)
if(t[j][x]!=t[j][y]){
val=min(val,D[j][x]);
val=min(val,D[j][y]);
x=t[j][x];
y=t[j][y];
}
val=min(val,D[0][x]);
val=min(val,D[0][y]);
if(i<=p)
fout<<val<<"\n";
x=xi;
y=yi;
x=(x*a+y*b)%n+1;
y=(y*c+val*d)%n+1;
}
return 0;
}