Cod sursa(job #2923099)

Utilizator Data 11 septembrie 2022 16:05:51 Atac 90 cpp-64 done Arhiva de probleme 1.64 kb
``````#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;

/*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=1e6,i,j,level;
if(lev[x]<lev[y])
swap(x,y);
level=lev[x]-lev[y];
for(i=0;i<15;i++)
{
if(level & (1<<i))
{
kon=min(kon,rmq[i][x]);
x=t[i][x];
}
}
for(i=14;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;
}
``````