Pagini recente » Cod sursa (job #154670) | Cod sursa (job #1934567) | Cod sursa (job #2254192) | Cod sursa (job #416049) | Cod sursa (job #1585746)
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
vector <pair<int, int> > G[32005];
vector <int> fir[32005];
int in, rmq[18][32005*2+1], lg[32005*2+1], i, n, m, p, u, v, j, x, y, fx, fy, z, a, b, c, d, r, mn, i1, i2;
bool viz[32005];
void dfs(int node)
{
viz[node]=1;
//fir[node].push_back(in+1);
for(int i=0;i<G[node].size();i++)
{
if(!viz[G[node][i].first])
{
in++;
fir[G[node][i].first].push_back(in+1);
rmq[0][in]=G[node][i].second;
dfs(G[node][i].first);
rmq[0][++in]=G[node][i].second;
fir[node].push_back(in+1);
}
}
/*if(G[node].size()==1)
in--;*/
}
int query(int x, int y)
{
int dist=y-x;
int put=lg[dist];
if((1<<put)==dist)
{
return rmq[put][x];
}
else
return min(rmq[put][x],rmq[put][y-(1<<put)+1]);
}
int main()
{
fin>>n>>m>>p;
for(i=2;i<=n;i++)
{
fin>>u>>v;
G[i].push_back(make_pair(u,v));
G[u].push_back(make_pair(i,v));
}
in=0;
fir[1].push_back(1);
dfs(1);
fir[1].push_back(in);
for(i=2;i<in;i++)
lg[i]=lg[i/2]+1;
for(i=1;(1<<i)<in;i++)
{
for(j=1;j+(1<<i)-1<in;j++)
{
rmq[i][j]=min(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
}
}
fin>>x>>y>>a>>b>>c>>d;
r=m;
for(i=1;i<=m;i++)
{
if(x!=y)
{
mn=in;
for(i1=0;i1<fir[x].size();i1++)
{
for(i2=0;i2<fir[y].size();i2++)
{
if(abs(fir[x][i1]-fir[y][i2])<mn)
{
mn=abs(fir[x][i1]-fir[y][i2]);
fx=fir[x][i1];
fy=fir[y][i2];
}
}
}
if(fx>fy)
swap(fx,fy);
z=query(fx,fy);
}
else
{
z=0;
}
if(r<=p)
{
fout<<z<<'\n';
}
r--;
x=(x*a+y*b)%n+1;
y=(y*c+z*d)%n+1;
}
return 0;
}