Pagini recente » Cod sursa (job #2448805) | Cod sursa (job #838779) | Cod sursa (job #669554) | Cod sursa (job #898946) | Cod sursa (job #1073264)
#include <fstream>
#include <vector>
#define MAXN 32005
#define MAXLOGN 17
#define INF 1000000
using namespace std;
ifstream f("atac.in");
ofstream g("atac.out");
int n,m,p,x,y,a,b,c,d,sol,cst,tata[MAXN][MAXLOGN],mn[MAXN][MAXLOGN],lvl[MAXN],xx,yy;
vector< pair<int,int> > G[MAXN];
void DFS(int nod);
inline int MIN(int x1,int x2){
return (x1<x2)?x1:x2;}
int main()
{
int i,j;
f>>n>>m>>p;
for(i=2;i<=n;i++){
f>>x>>cst;
G[i].push_back(make_pair(x,cst));
G[x].push_back(make_pair(i,cst));}
f>>x>>y>>a>>b>>c>>d;
tata[1][0]=-1;
DFS(1);
for(i=1;i<=m;i++){
xx=x;yy=y;
sol=INF;
if(lvl[yy]>lvl[xx])
swap(xx,yy);
for(j=MAXLOGN-1;j>=0;j--)
if(lvl[xx]-(1<<j)>=lvl[yy]){
if(mn[xx][j]<sol)
sol=mn[xx][j];
xx=tata[xx][j];}
if(xx==yy){
if(sol==INF)
sol=0;
if(i+p>m)
g<<sol<<'\n';
x=(x*a+y*b)%n+1;
y=(y*c+sol*d)%n+1;
continue;}
for(j=MAXLOGN-1;j>=0;j--)
if(tata[xx][j]!=tata[yy][j]){
if(mn[xx][j]<sol)
sol=mn[xx][j];
if(mn[yy][j]<sol)
sol=mn[yy][j];
xx=tata[xx][j];
yy=tata[yy][j];}
if(mn[xx][0]<sol)
sol=mn[xx][0];
if(mn[yy][0]<sol)
sol=mn[yy][0];
if(i+p>m)
g<<sol<<'\n';
x=(x*a+y*b)%n+1;
y=(y*c+sol*d)%n+1;}
f.close();
g.close();
return 0;
}
void DFS(int nod){
int i,j;
for(i=0;i<G[nod].size();i++){
xx=G[nod][i].first;
if(!tata[xx][0]){
lvl[xx]=lvl[nod]+1;
tata[xx][0]=nod;
mn[xx][0]=G[nod][i].second;
yy=nod;
for(j=1;tata[yy][j-1]>0;j++){
tata[xx][j]=tata[yy][j-1];
mn[xx][j]=MIN(mn[xx][j-1],mn[yy][j-1]);
yy=tata[xx][j];}
DFS(xx);}}}