Pagini recente » Cod sursa (job #2560607) | Cod sursa (job #2688294) | Cod sursa (job #1169779) | Cod sursa (job #2945711) | Cod sursa (job #2409346)
#include <bits/stdc++.h>
#define Dim 32007
#define MAX 100006
using namespace std;
ifstream f("atac.in");
ofstream g("atac.out");
int N,M,P,X,Y,X1,Y1,A,B,C,D,Z,a,b;
int E[2*Dim],Prim[Dim],G[2*Dim],cnt;
int rmq[16][Dim],Deep[Dim],Cont[Dim],maxim;
int vertex,low_scad,Cost[Dim],bazaA,bazaB;
typedef pair<int,int> pi;
bool viz[Dim],viz2[Dim],viz3[Dim];
vector < pi > V[Dim];
set < pi > S[Dim];
set < pi > ::iterator it;
void DFS(int nod,int niv)
{
viz[nod]=1;
G[++cnt]=niv;
E[cnt]=nod;
Prim[nod]=cnt;
for(unsigned int i=0;i<V[nod].size();i++)
{
int vecin=V[nod][i].first;
if(!viz[vecin])
{
DFS(vecin,niv+1);
E[++cnt]=nod;
G[cnt]=niv;
}
}
}
void RMQ()
{
for(int i=1;i<=cnt;i++) rmq[0][i]=i;
for(int i=1;(1<<i)<=cnt;i++)
for(int j=1;j+(1<<i)-1<=cnt;j++)
{
int a=rmq[i-1][j];
int b=rmq[i-1][j+(1<<(i-1))];
if(G[a]<=G[b]) rmq[i][j]=a;
else rmq[i][j]=b;
}
}
void DFS2(int nod)
{
viz2[nod]=1;
maxim++;
Cont[nod]=maxim;
for(unsigned int i=0;i<V[nod].size();i++)
{
int vecin=V[nod][i].first;
if(!viz2[vecin]) DFS2(vecin);
}
}
void BFS()
{
queue < pi > qu;
viz3[1]=0;
Deep[1]=1;
qu.push({1,1});
S[1].insert({1,1});
while(!qu.empty())
{
int nod=qu.front().first;
int niv=qu.front().second+1;
qu.pop();
viz3[nod]=1;
for(unsigned int i=0;i<V[nod].size();i++)
{
int vecin=V[nod][i].first;
if(!viz3[vecin])
{
viz3[vecin]=1;
Deep[vecin]=niv;
S[niv].insert({Cont[vecin],vecin});
qu.push({vecin,niv});
}
}
}
}
int main()
{
f>>N>>M>>P;
for(int i=2;i<=N;i++)
{
f>>a>>b;
V[i].push_back({a,b});
V[a].push_back({i,b});
Cost[i]=b;
}
DFS(1,1);
RMQ();
DFS2(1);
BFS();
//for(int i=1;i<=N;i++) cout<<i<<" "<<Cost[i]<<'\n';
f>>X>>Y>>A>>B>>C>>D;
for(int i=1;i<=M;i++)
{
a=Prim[X]; b=Prim[Y];
if(a>b) swap(a,b);
int lg=log2(b-a+1);
int poza=rmq[lg][a];
int pozb=rmq[lg][b-(1<<lg)+1];
if(G[poza]<=G[pozb]) vertex=E[poza];
else vertex=E[pozb];
bazaA=X; bazaB=Y;
int limit=Deep[X]-Deep[vertex];
int recent=X;
Z=MAX;
//if(i==1) cout<<X<<" "<<Deep[X]<<" "<<vertex<<" "<<Deep[vertex]<<" "<<limit<<'\n';
for(int j=1;j<=limit;j++)
{
Z=min(Z,Cost[X]);
//if(i==1) cout<<X<<" "<<bazaA<<" "<<bazaB<<" "<<Cost[X]<<'\n';
int level=Deep[recent]-1;
int ID=Cont[recent];
it=S[level].lower_bound({ID,level});
it--;
X=it->second;
recent=X;
//if(i==2) cout<<j<<" "<<limit<<'\n';
}
//cout<<i<<" "<<X<<" "<<Y<<'\n';
limit=Deep[Y]-Deep[vertex];
recent=Y;
X=Y;
for(int j=1;j<=limit;j++)
{//cout<<i<<" "<<vertex<<" "<<j<<" "<<recent<<" "<<X<<" "<<limit<<'\n';
Z=min(Z,Cost[X]);
//if(i==1) cout<<X<<" "<<bazaA<<" "<<bazaB<<" "<<Cost[X]<<'\n';
int level=Deep[recent]-1;
int ID=Cont[recent];
it=S[level].lower_bound({ID,level});
it--;
X=it->second;
recent=X;
}
if(i>=M-P+1) g<<Z<<'\n';
X1=(bazaA*A+bazaB*B)%N; X1++;
Y1=(C*bazaB+Z*D)%N; Y1++;
X=X1;
Y=Y1;
// cout<<i<<" "<<bazaA<<" "<<bazaB<<" "<<X<<" "<<Y<<" "<<Z<<'\n';
// cout<<bazaA<<" "<<bazaB<<" "<<X<<" "<<Y<<" "<<Z<<'\n';
}
return 0;
}