Pagini recente » Cod sursa (job #212521) | Cod sursa (job #54895) | Cod sursa (job #735594) | Cod sursa (job #1726890) | Cod sursa (job #2633896)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in ("atac.in");
ofstream out("atac.out");
const int oo=2e9, nmax=32003;
int n, m, p, X, Y, A, B, C, D, x, cost;
short loga[nmax], level[nmax];
vector <pair <short, int> > muchii[nmax];
short sparse[nmax][17];
int dp[nmax][17];
void dfs(int nod)
{
for(int put=1; level[nod]-(1<<put)>=1; put++)
{
int ancestor=sparse[nod][put-1];
sparse[nod][put]=sparse[ancestor][put-1];
dp[nod][put]=min(dp[nod][put-1], dp[ancestor][put-1]);
}
for(auto & x:muchii[nod])
if(!level[x.first])
{
sparse[x.first][0]=nod;
dp[x.first][0]=x.second;
level[x.first]=level[nod]+1;
dfs(x.first);
}
}
inline int find_sol(int i, int j)
{
if(i==j) return 0;
if(level[i]<level[j]) swap(i, j);
int levi=level[i], levj=level[j], mini=oo;
int put=loga[levi-levj];
while(levi>levj)
{
if(levi-(1<<put)>=levj)
mini=min(mini, dp[i][put]), levi-=(1<<put), i=sparse[i][put];
put--;
}
put=loga[levi-1];
for( ;put>0; put--)
if(sparse[i][put]!=sparse[j][put])
mini=min({mini, dp[i][put], dp[j][put]}), levi-=(1<<put), i=sparse[i][put], j=sparse[j][put];
while(i!=j)
{
mini=min({mini, dp[i][0], dp[j][0]});
i=sparse[i][0]; j=sparse[j][0];
}
return mini;
}
int main()
{
loga[1]=0;
in>>n>>m>>p;
for(int i=2; i<=n; i++)
loga[i]=loga[i/2]+1;
for(int i=2; i<=n; i++)
{
in>>x>>cost;
muchii[i].push_back({x, cost});
muchii[x].push_back({i, cost});
}
level[1]=1; dfs(1);
in>>X>>Y>>A>>B>>C>>D;
for(int q=1; q<=m; q++)
{
int nrB=find_sol(X, Y);
if(q>=m-p+1)
out<<nrB<<"\n";
X=((long long)X*A+(long long)Y*B) % n + 1;
Y=((long long)Y*C+(long long)nrB*D) % n + 1;
}
return 0;
}