Pagini recente » Cod sursa (job #831403) | Cod sursa (job #2117578) | Cod sursa (job #917601) | Cod sursa (job #2738711) | Cod sursa (job #1734333)
#include <iostream>
#include<fstream>
#include<vector>
#include<bitset>
using namespace std;
const int nmax=32000;
int rmq[18][4*nmax+5],level[nmax+5],dif,niv,n,m,p,U,val,i,k,first[nmax+5],a[18][nmax+5],lg[2*nmax+5],j,unu,doi,aa,b,ce,d,x,y,z,z1,z2,nod,drmin[18][nmax+5],drum,nr;
bitset<nmax+5> viz;
vector<int> v[nmax+5],c[nmax+5];
void dfs(int x,int lev)
{
viz[x]=1;
k++;
level[x]=lev;
rmq[0][k]=x;
first[x]=k;
for(int i=0;i<v[x].size();i++)
{
if(!viz[v[x][i]])
{
a[0][v[x][i]]=x;
drmin[0][v[x][i]]=c[x][i];
dfs(v[x][i],lev+1);
k++;
rmq[0][k]=x;
}
}
}
void buildrmq()
{
for(i=1;(1<<i)<=k;i++)
for(j=1;j<=k-(1<<i)+1;j++)
{
if(level[rmq[i-1][j]]<level[rmq[i-1][j+(1<<(i-1))]]) rmq[i][j]=rmq[i-1][j];
else rmq[i][j]=rmq[i-1][j+(1<<(i-1))];
}
}
int lca(int x,int y)
{
unu=first[x];doi=first[y];
if(unu>doi) swap(unu,doi);
niv=lg[doi-unu+1];
dif=doi-unu+1-(1<<niv);
if(level[rmq[niv][unu]]<level[rmq[niv][unu+dif]]) return rmq[niv][unu];
return rmq[niv][unu+dif];
}
void buildstructure()
{
for(i=1;i<=lg[n];i++)
for(j=1;j<=n;j++)
{
a[i][j]=a[i-1][a[i-1][j]];
drmin[i][j]=min(drmin[i-1][j],drmin[i-1][a[i-1][j]]);
}
}
int query(int x)
{
nr=level[x]-level[nod];
int j;int cpy=x;
drum=(1<<30);
while(nr!=0)
{
j=lg[((nr^(nr-1))&nr)];
if(drmin[j][x]<drum)
drum=drmin[j][x];
nr-=(1<<j);
x=a[j][x];
}
x=cpy;
return drum;
}
int main()
{
ifstream f("atac.in");
ofstream g("atac.out");
f>>n>>m>>p;
for(i=2;i<=n;i++)
{
f>>U>>val;
v[i].push_back(U);
c[i].push_back(val);
v[U].push_back(i);
c[U].push_back(val);
}
dfs(1,1);
for(i=2;i<=k;i++)
lg[i]=lg[i/2]+1;
f>>x>>y>>aa>>b>>ce>>d;
z=0;
buildrmq();
buildstructure();
for(i=1;i<=m;i++)
{
nod=lca(x,y);
z1=query(x);
z2=query(y);
z=min(z1,z2);
if(x==y) z=0;
if(i>=m-p+1) g<<z<<'\n';
x=(x*aa+y*b)%n+1;
y=(y*ce+z*d)%n+1;
}
return 0;
}