Pagini recente » Cod sursa (job #749330) | Cod sursa (job #1941643) | Cod sursa (job #1303893) | Cod sursa (job #1987055) | Cod sursa (job #2633888)
#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;
int loga[nmax], level[nmax];
vector <pair <short, int> > muchii[nmax];
vector <short> sparse[nmax];
vector <int> dp[nmax];
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=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--; ///puterea trebuia scazuta...
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});
}
dfs(1, 0, 1, 0);
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;
}