Pagini recente » Cod sursa (job #3133672) | Cod sursa (job #6726) | Cod sursa (job #309097) | Cod sursa (job #3263254) | Cod sursa (job #929809)
Cod sursa(job #929809)
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
long i,j,n,m,m1,m2,A,B,C,D,Z,nr,p;
long tata[32001],c[32001],niv[32001];
struct muchii
{
int x,y,cost;
};
muchii a[32001];
bool cmp(muchii a,muchii b)
{
return a.cost>b.cost;
}
void aflanivel(int x)
{
if(tata[x]==x)
return ;
aflanivel(tata[x]);
niv[x]=niv[tata[x]]+1;
}
int componenta(int x)
{
while(x!=tata[x])
x=tata[x];
return x;
}
int main()
{
ifstream f("atac.in");
ofstream g("atac.out");
f>>n>>m>>p;
for(i=2;i<=n;++i)
{
f>>m1>>m2;
a[i-1].x=m1;
a[i-1].y=i;
a[i-1].cost=m2;
tata[i]=i;
}
tata[1]=1;
sort(a+1,a+n,cmp);
for(i=1;i<n;++i)
{
m1=componenta(a[i].x);
m2=componenta(a[i].y);
if(m1!=m2)
{
tata[m2]=m1;
c[m2]=a[i].cost;
}
}
for(i=1;i<=n;++i)
if(!niv[i])
aflanivel(i);
f>>m1>>m2>>A>>B>>C>>D;
while(m)
{
Z=1<<20;
int xx=m1,yy=m2;
while(niv[m1]>niv[m2])
{
Z=min(Z,c[m1]);
m1=tata[m1];
}
while(niv[m2]>niv[m1])
{
Z=min(Z,c[m2]);
m2=tata[m2];
}
while(m1!=m2)
{
Z=min(Z,min(c[m1],c[m2]));
m1=tata[m1];
m2=tata[m2];
}
if(Z==1<<20)
Z=0;
if(m<=p)
g<<Z<<"\n";
m1=(A*xx+B*yy)%n+1;
m2=(C*yy+D*Z)%n+1;
--m;
}
return 0;
}