Pagini recente » Cod sursa (job #1617384) | Cod sursa (job #1430249) | Clasament eusebiu_oji_2015_cls11-12 | Cod sursa (job #481768) | Cod sursa (job #1096321)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
#define MAX 32100
int RMQ[2*MAX][18], par[MAX][17], stramosi[MAX][17], pa[MAX], dr, poz[MAX], nivel[MAX], viz[MAX], costpa[MAX], stiva[MAX], g, log[MAX*2];
vector <int> G[MAX];
int lca(int x, int y)
{
if(x>y)
swap(x, y);
int g=log[y-x];
if(nivel[RMQ[x][g]]<nivel[RMQ[y-(1<<g)+1][g]])
return RMQ[x][g];
return RMQ[y-(1<<g)+1][g];
}
int up(int nod)
{
if(pa[nod])
return up(pa[nod]);
return nod;
}
void introdu(int nod, int depth)
{
dr++;
RMQ[dr][0]=nod;
poz[nod]=dr;
nivel[nod]=depth;
}
int euler(int nod, int depth)
{
viz[nod]=1;
introdu(nod, depth);
for(int i=0;i<G[nod].size();i++)
{
if(!viz[G[nod][i]])
{
euler(G[nod][i], depth+1);
introdu(nod, depth);
}
}
}
void dfs(int nod)
{
stiva[++g]=nod;
viz[nod]=0;
int i;
stramosi[nod][0]=pa[nod];
for(i=1;(1<<i)<g;i++)
{
par[nod][i]=min(par[nod][i-1], par[stiva[g-(1<<(i-1))]][i-1]);
stramosi[nod][i]=stramosi[g-(1<<(i-1))][i-1];
}
for(i=0;i<G[nod].size();i++)
{
if(viz[G[nod][i]])
{
dfs(G[nod][i]);
}
}
--g;
}
int nr_bombe(int nod, int x)
{
int rez=1<<29;
int i;
for(i=0;(1<<i)<=x;i++)
{
if(x&(1<<i))
{
rez=min(rez, par[nod][i]);
nod=stramosi[nod][i];
}
}
return rez;
}
int main()
{
int n, m, p, i, u, v, l, j, X, Y, A, B, C, D, nod, Xp, Yp, Z;
fin>>n;
fin>>m>>p;
for(i=2;i<=n;i++)
{
fin>>u>>v;
G[u].push_back(i);
pa[i]=u;
par[i][0]=v;
}
l=up(1);
euler(l, 0);
for(i=2;i<=dr;i++)
{
log[i]=log[i/2]+1;
}
for(j=1;(1<<j)<=dr;j++)
{
for(i=1;i+(1<<(j-1))<=dr;i++)
{
if(nivel[RMQ[i][j-1]]<nivel[RMQ[i+(1<<(j-1))][j-1]])
RMQ[i][j]=RMQ[i][j-1];
else
RMQ[i][j]=RMQ[i+(1<<(j-1))][j-1];
}
}
dfs(l);
fin>>X>>Y>>A>>B>>C>>D;
while(m--)
{
//cout<<X<<" "<<Y<<" ";
nod=lca(poz[X], poz[Y]);
//cout<<nod<<" ";
Z=min(nr_bombe(X, nivel[X]-nivel[nod]),nr_bombe(Y, nivel[Y]-nivel[nod]) );
if(X==Y)
Z=0;
if(m<p)
fout<<Z<<"\n";
Xp=((X*A+Y*B)%n)+1;
Yp=((Y*C+Z*D)%n)+1;
X=Xp;
Y=Yp;
}
}