Pagini recente » Cod sursa (job #495206) | Borderou de evaluare (job #3296666) | Cod sursa (job #3348574) | Cod sursa (job #221829) | Cod sursa (job #3343776)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream cin("atac.in");
ofstream cout("atac.out");
int n,q,p;
int N,idx,mxb;
int X,Y,a,b,c,d,Z;
struct idg
{
int y,w;
};
vector<idg> G;
vector<int> nxt,top,lvl;
vector<int> anc[18],dp[18];
void add_edge(int x,int y,int w)
{
idx++;
G[idx]={y,w};
nxt[idx]=top[x];
top[x]=idx;
}
void dfs(int x,int tata)
{
lvl[x]=lvl[tata]+1;
for(int i=top[x];i;i=nxt[i])
{
auto [y,w]=G[i];
if(y==tata)
continue;
dp[0][y]=w;
anc[0][y]=x;
dfs(y,x);
}
}
int min_lant(int x,int y)
{
if(x==y)
return 0;
int ans=2e9;
if(lvl[x]<lvl[y])
swap(x,y);
int dif=lvl[x]-lvl[y];
for(int i=0;i<=mxb;i++)
if(dif&(1<<i))
{
ans=min(ans,dp[i][x]);
x=anc[i][x];
}
for(int i=mxb;i>=0;i--)
if(anc[i][x]!=anc[i][y])
{
ans=min(ans,dp[i][x]);
x=anc[i][x];
ans=min(ans,dp[i][y]);
y=anc[i][y];
}
if(x!=y)
{
ans=min(ans,dp[0][x]);
ans=min(ans,dp[0][y]);
}
return ans;
}
int main()
{
cin>>n>>q>>p;
G=vector<idg>(2*n+1);
nxt=vector<int>(2*n+1);
top=lvl=vector<int>(n+1);
for(int i=2;i<=n;i++)
{
int x,y,w;
cin>>y>>w;
x=i;
add_edge(x,y,w);
add_edge(y,x,w);
}
mxb=log2(n)+1;
for(int i=0;i<=mxb;i++)
{
anc[i]=vector<int>(n+1);
dp[i]=vector<int>(n+1);
}
dfs(1,0);
for(int i=1;i<=mxb;i++)
{
for(int j=1;j<=n;j++)
{
anc[i][j]=anc[i-1][anc[i-1][j]];
dp[i][j]=min(dp[i-1][j],dp[i-1][anc[i-1][j]]);
}
}
int ans=0;
cin>>X>>Y>>a>>b>>c>>d;
for(int i=1;i<=q;i++)
{
ans=min_lant(X,Y);
X=(X*a+Y*b)%n+1;
Y=(Y*c+ans*d)%n+1;
if(i>=q-p+1)
cout<<ans<<"\n";
}
return 0;
}