Pagini recente » Cod sursa (job #2501050) | Cod sursa (job #117255) | Cod sursa (job #885778) | Cod sursa (job #2832943) | Cod sursa (job #2923098)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream fin ("atac.in");
ofstream fout ("atac.out");
const int NMAX=32005;
const int NMAX1=20;
vector<int> v[NMAX];
int rmq[NMAX1][NMAX];
int t[NMAX1][NMAX];
int lev[NMAX];
int ti[NMAX];
int to[NMAX];
int n,m,kon;
bool ancestor(int x,int y)
{
return ti[x]<=ti[y] && to[x]>=to[y];
}
void dfs(int x)
{
ti[x]=++kon;
for(auto i:v[x])
dfs(i);
to[x]=++kon;
}
void dfs2(int p, int x)
{
lev[p]=x;
for(auto i : v[p])
dfs2(i,x+1);
}
void precalculare_min()
{
int e,i;
dfs2(1,0);
for(e=1;(1<<e)<=n;e++)
{
for(i=1;i<=n;i++)
{
t[e][i]=t[e-1][t[e-1][i]];
rmq[e][i]=min(rmq[e-1][i],rmq[e-1][t[e-1][i]]);
}
}
}
int solve(int x, int y)
{
int kon=1e9,i,j,level;
level=abs(lev[x]-lev[y]);
if(lev[x]<lev[y])
swap(x,y);
for(i=0;i<20;i++)
{
if(level & (1<<i))
{
kon=min(kon,rmq[i][x]);
x=t[i][x];
}
}
for(i=20;i>=0;i--)
{
if(t[i][x]!=t[i][y])
{
kon=min(kon,rmq[i][x]);
kon=min(kon,rmq[i][y]);
x=t[i][x];
y=t[i][y];
}
}
if(x!=y)
{
kon=min(kon,rmq[0][x]);
kon=min(kon,rmq[0][y]);
}
return kon;
}
int main()
{
int p,i,j,x,y,a,b,c,d,z,hp;
fin>>n >>m>>p;
for(i=2;i<=n;i++)
{
fin>>x>>hp;
v[x].push_back(i);
rmq[0][i]=hp;
t[0][i]=x;
}
precalculare_min();
fin>>x>>y>>a>>b>>c>>d;
for(i=1;i<=m;i++)
{
if(x==y)
z=0;
else
z=solve(x, y);
if(i>m-p)
fout<<z<<"\n";
x=(x*a+y*b)%n+1;
y=(y*c+z*d)%n+1;
}
return 0;
}