Pagini recente » Sandbox (cutiuţa cu năsip) | Sandbox (cutiuţa cu năsip) | Sandbox (cutiuţa cu năsip) | Cod sursa (job #1092620) | Cod sursa (job #2988814)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
#define nmax 32005
#define pmax 500005
vector<pair<int,int> > g[nmax];
int parc[3*nmax],h[3*nmax],frst[nmax];
int viz[nmax];
int minim[3*nmax][70];
int nr=0;
int n;
int inaltime[nmax];
void dfs(int nod,int nivel)
{
parc[++nr]=nod;
h[nr]=nivel;
inaltime[nod]=nivel;
frst[nod]=nr;
viz[nod]=1;
for(int i=0; i<g[nod].size(); i++)
{
int s=g[nod][i].first;
if(!viz[s])
{
dfs(s,nivel+1);
parc[++nr]=nod;
h[nr]=nivel;
}
}
}
void rmq()
{
for(int i=1; i<=nr; i++)minim[i][0]=i;
for(int l=1; (1<<l)<=nr; l++)
{
int pp=1<<l;
pp=pp/2;
for(int i=1; i+pp<=nr; i++)
{
if(h[minim[i][l-1]]<=h[minim[i+pp+1][l-1]])
{
minim[i][l]=minim[i][l-1];
}
else
{
minim[i][l]=minim[i+pp+1][l-1];
}
}
}
}
int rezultat;
int altdfs(int nod,int stramos)
{
if(nod ==stramos) return rezultat;
for(int i=0; i<g[nod].size(); i++)
{
int s=g[nod][i].first;
if(inaltime[s]<inaltime[nod]&&inaltime[s]>=inaltime[stramos])
{
rezultat=min(rezultat,g[nod][i].second);
altdfs(s,stramos);
}
}
}
int vezi(int x, int y)
{
if(frst[x]>frst[y])swap(x,y);
int l=abs(frst[x]-frst[y]);
l=log2(l);
int stramos;
if(h[minim[frst[x]][l]]<h[minim[frst[y]-(1<<l)+1][l]])
{
stramos=parc[minim[frst[x]][l]];
}
else
{
stramos=parc[minim[frst[y]-(1<<l)+1][l]];
}
rezultat=INT_MAX;
altdfs(y,stramos);
int aux=rezultat;
rezultat=INT_MAX;
altdfs(x,stramos);
return min(rezultat,aux);
}
int main()
{
int m,p,i,u,v,x,y,a,b,c,d;
fin>>n>>m>>p;
for(i=2; i<=n; i++)
{
fin>>u>>v;
g[i].push_back({u,v});
g[u].push_back({i,v});
}
fin>>x>>y>>a>>b>>c>>d;
frst[1]=1;
dfs(1,1);
rmq();
for(i=1; i<=m-p; i++)
{
int z=vezi(x,y);
x=(x*a+y*b)%n+1;
y=(y*c+z*d)%n+1;
}
for(i=m-p+1; i<=m; i++)
{
int z=vezi(x,y);
fout<<z<<'\n';
x=(x*a+y*b)%n+1;
y=(y*c+z*d)%n+1;
}
return 0;
}