Pagini recente » Cod sursa (job #2442029) | Cod sursa (job #2479993) | Cod sursa (job #218060) | Cod sursa (job #2403479) | Cod sursa (job #2633883)
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream in ("atac.in");
ofstream out("atac.out");
const int oo=2e9;
int n, m, p, X, Y, A, B, C, D, x, cost;
vector <short> level;
vector <vector <pair <short, int> > > muchii;
vector <vector <short> > sparse;
vector <vector <int> > dp;
void dfs(int nod, int ant, int lev, int cost)
{
sparse[nod].push_back(ant);
dp[nod].push_back(cost);
level[nod]=lev;
for(int put=1; lev-(1<<put)>=1; put++)
{
int ancestor=sparse[nod][put-1];
sparse[nod].push_back(sparse[ancestor][put-1]);
dp[nod].push_back(min(dp[nod][put-1], dp[ancestor][put-1]));
}
for(auto & x:muchii[nod])
if(!level[x.first])
dfs(x.first, nod, lev+1, x.second);
}
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=log2(levi-levj);
while(levi>levj)
if(levi-(1<<put)>=levj)
mini=min(mini, dp[i][put]), levi-=(1<<put), i=sparse[i][put];
put=log2(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()
{
in>>n>>m>>p;
muchii.resize(n+1); level.resize(n+1);
sparse.resize(n+1); dp.resize(n+1);
for(int i=2; i<=n; i++)
{
in>>x>>cost;
muchii[i].push_back({x, cost});
muchii[x].push_back({i, cost});
}
dfs(1, 0, 1, 0);
muchii.clear(); muchii.shrink_to_fit();
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=(X*A+Y*B) % n + 1;
Y=(Y*C+nrB*D) % n + 1;
}
return 0;
}