Pagini recente » Cod sursa (job #2985013) | Diferente pentru problema/seti intre reviziile 1 si 2 | Cod sursa (job #1069869) | Cod sursa (job #2804570) | Cod sursa (job #3344867)
#include <fstream>
#include <vector>
#define NMAX 32002
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
int N,M,P,X,Y,A,B,C,D,Z,tata[NMAX],nivel[NMAX];
vector<pair<int,int>> tree[NMAX];
vector<vector<pair<int,int>>> up(NMAX,vector<pair<int,int>>(17));
void citire()
{
fin>>N>>M>>P;
int val;
for(int i=2; i<=N; i++)
{
fin>>tata[i]>>val;
tree[tata[i]].push_back({i,val});
}
fin>>X>>Y>>A>>B>>C>>D;
}
void DFS(int nod)
{
for(int i=0; i<tree[nod].size(); i++)
{
int next_nod=tree[nod][i].first;
int drum=tree[nod][i].second;
nivel[next_nod]=nivel[nod]+1;
up[next_nod][0].first=nod;
up[next_nod][0].second=drum;
for(int j=1; j<=16; j++)
{
up[next_nod][j].first=up[up[next_nod][j-1].first][j-1].first;
up[next_nod][j].second=min(up[next_nod][j-1].second,up[up[next_nod][j-1].first][j-1].second);
}
DFS(next_nod);
}
}
int distrugere_drum(int x, int y)
{
int ans=10000000;
if(x==y)
{
return 0;
}
if(nivel[x]<nivel[y])
{
swap(x,y);
}
int k=nivel[x]-nivel[y];
for(int j=16; j>=0; j--)
{
if(k&(1<<j))
{
ans=min(ans,up[x][j].second);
x=up[x][j].first;
}
}
if(x==y)
{
return ans;
}
for(int j=16; j>=0; j--)
{
if(up[x][j].first!=up[y][j].first)
{
ans=min(ans,up[x][j].second);
ans=min(ans,up[y][j].second);
x=up[x][j].first;
y=up[y][j].first;
}
}
ans=min(ans,up[x][0].second);
ans=min(ans,up[y][0].second);
return ans;
}
int main()
{
citire();
DFS(1);
Z=distrugere_drum(X,Y);
if(P==M)
{
fout<< Z << "\n";
}
for(int i=2; i<=M; i++)
{
X=(long long)(X*A+Y*B)%N+1;
Y=(long long)(Y*C+Z*D)%N+1;
Z=distrugere_drum(X,Y);
if(M-P+1<=i)
{
fout<< Z << "\n";
}
}
return 0;
}