Pagini recente » Cod sursa (job #2449854) | Cod sursa (job #2466132) | Cod sursa (job #1481560) | Cod sursa (job #1554361) | Cod sursa (job #29283)
Cod sursa(job #29283)
#include "fstream.h"
ifstream f("atac.in");
ofstream g("atac.out");
#define N 32001
#define M 500001
struct muchie
{
int n1,n2,c;
}mu[N];
long m,p,n,a,b,c,d,viz[N],co[N],v[M],x,y;
void citire()
{
int i;
long cost;
f>>n>>m>>p;
for(i=1;i<=n-1;i++)
{
f>>x>>cost;
mu[i].n1=x;
mu[i].n2=i+1;
mu[i].c=cost;
viz[i]=1;
}
f>>x>>y>>a>>b>>c>>d;
}
int pivot(int l,int r,muchie a[])
{
int i;
for(i=l;i<r;i++)
if(a[i].c!=a[i+1].c)
if(a[i+1].c>a[i].c)
return i+1;
else
return i;
return -1;
}
int div(int l,int r,int p,muchie a[])
{
int i,j;
muchie aux;
i=l;
j=r;
do
{
aux=a[i];
a[i]=a[j];
a[j]=aux;
while(a[i].c<p)
i++;
while(a[j].c>=p)
j--;
}while(i<j);
return i;
}
void quicksort(int l,int r,muchie a[])
{
int k,p,index;
index=pivot(l,r,a);
if(index!=-1)
{
p=a[index].c;
k=div(l,r,p,a);
quicksort(l,k-1,a);
quicksort(k,r,a);
}
}
int cnx()
{
int i,j,min,max;
for(i=1;i<=n;i++)
co[i]=i;
for(j=1;j<=n-1;j++)
if(viz[j])
if(co[mu[j].n1]!=co[mu[j].n2])
{
if(co[mu[j].n1]<co[mu[j].n2])
{
min=co[mu[j].n1];
max=co[mu[j].n2];
}
else
{
min=co[mu[j].n2];
max=co[mu[j].n1];
}
for(i=1;i<=n;i++)
if(co[i]==max)
co[i]=min;
}
if(co[x]!=co[y])
return 0;
return 1;
}
int main()
{
citire();
long i,per,q;
quicksort(1,n-1,mu);
for(i=1;i<=n;i++)
viz[i]=1;
for(per=1;per<=m;per++)
{
for(i=1;i<n;i++)
{
viz[i]=0;
q=i;
if(!cnx())
{
i=n;
viz[q]=1;
}
viz[q]=1;
}
v[per]=mu[q].c;
x=((a*x+y*b)%n)+1;
y=((y*c+d*v[per])%n)+1;
}
for(i=m;i>=p;i++)
g<<v[i]<<"\n";
return 0;
}