Cod sursa(job #40658)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 27 martie 2007 17:01:36
Problema Atac Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.33 kb
# include <stdio.h>
# include <stdlib.h>

const long int MAXN=32000;

typedef struct NOD_ARBDINT {long int lca; NOD_ARBDINT *stga,*drta;};
NOD_ARBDINT *rad_lca;
typedef struct NOD {long int niv,ffiu,nfrate,cost,tata;};
NOD nod[MAXN+1];
int sel[MAXN+1];
long int chain[3*MAXN+3];
long int first[MAXN+1];
long int n,m,p,a,b,c,d,xi,yi,rad,chainlen;
typedef struct NODANC {long int min,anc;};
NODANC anc[MAXN+1][16];

void add(long int dest, long int node, long int cost)
{
nod[node].tata=dest;
nod[node].cost=cost;
nod[node].niv=nod[dest].niv+1;
long int p;
if (nod[dest].ffiu==0)
	nod[dest].ffiu=node;
else
	{
	p=nod[dest].ffiu;
	while (nod[p].nfrate!=0) p=nod[p].nfrate;
	nod[p].nfrate=node;
	}
}

void citire()
{
FILE *f=fopen("atac.in","r");
fscanf(f,"%ld%ld%ld",&n,&m,&p);
long int i,bb,cost;
for (i=2;i<=n;i++)
	{
	fscanf(f,"%ld%ld",&bb,&cost);
	if (sel[i]) add(i,bb,cost);
	else
		{
		if (i==2&&!sel[bb])
			{
			rad=bb;
			nod[rad].niv=1;
			}
		add(bb,i,cost);
		}
	}
fscanf(f,"%ld%ld%ld%ld%ld%ld",&xi,&yi,&a,&b,&c,&d);
fclose(f);
}

void find_chain(long int node)
{
long int p;
chain[++chainlen]=node;
p=nod[node].ffiu;
while (p)
	{
	find_chain(p);
	chain[++chainlen]=node;
	p=nod[p].nfrate;
	}
}

void aloca_arb_dint(long int li, long int lf, NOD_ARBDINT *p)
{
long int mij=(li+lf)/2;
NOD_ARBDINT *q;
if (li!=lf)
	{
	q=(NOD_ARBDINT*) malloc (sizeof(NOD_ARBDINT));
	(*q).lca=0;
	(*q).stga=(*q).drta=NULL;
	(*p).stga=q;
	aloca_arb_dint(li,mij,q);
	q=(NOD_ARBDINT*) malloc (sizeof(NOD_ARBDINT));
	(*q).lca=0;
	(*q).stga=(*q).drta=NULL;
	(*p).drta=q;
	aloca_arb_dint(mij+1,lf,q);
	}
}

void update(long int li, long int lf, long int a, NOD_ARBDINT *p)
{
long int mij=(li+lf)/2;
if (a==li&&a==lf) (*p).lca=chain[a];
else
	{
	if ( (*p).lca==0 || ( nod[(*p).lca].niv>nod[chain[a]].niv ) )
		(*p).lca=chain[a];
	if (a<=mij) update(li,mij,a,(*p).stga);
	else update(mij+1,lf,a,(*p).drta);
	}
}

void populate_arb_dint()
{
long int i;
for (i=1;i<=chainlen;i++)
	update(1,chainlen,i,rad_lca);
}

void print_ad(long int li, long int lf, NOD_ARBDINT *p)
{
printf("%ld %ld : %ld \n",li,lf,(*p).lca);
if ((*p).stga) print_ad(li,(li+lf)/2,(*p).stga);
if ((*p).drta) print_ad((li+lf)/2+1,lf,(*p).drta);
}

void prepare_nodes()
{
long int i;
for (i=1;i<=chainlen;i++)
	if (first[chain[i]]==0) first[chain[i]]=i;
}

long int min(long int a, long int b) {if (a>b) return b; return a;}
long int max(long int a, long int b) {if (a>b) return a; return b;}

void create_ancestors()
{
long int i;int ord;
for (i=1;i<=n;i++)
	{
	anc[i][0].anc=nod[i].tata;
	anc[i][0].min=nod[i].cost;
	}
for (ord=1;ord<=15;ord++)
	for (i=1;i<=n;i++)
		{
		long int stramos=anc[i][ord-1].anc;
		anc[i][ord].anc=anc[stramos][ord-1].anc;
		anc[i][ord].min=min(anc[i][ord-1].min,anc[stramos][ord-1].min);
		}
}

void scrie(FILE *g, long int value) {fprintf(g,"%ld\n",value);}

long int find_lca(long int a, long int b, long int li, long int lf, NOD_ARBDINT *p)
{
long int ww=-1,w=-1,mij=(li+lf)/2;
if (a<=li&&lf<=b) return (*p).lca;
if (a<=mij) ww=find_lca(a,b,li,mij,(*p).stga);
if (b>mij) w=find_lca(a,b,mij+1,lf,(*p).drta);
if (ww==-1) return w;
if (w==-1) return ww;
if (nod[ww].niv<nod[w].niv) w=ww;
return w;
}

long int find_nec_min(long int jos, long int sus)
{
if (jos==sus) return 10000000;
long int p=0;
while (nod[jos].niv-nod[sus].niv>=(long int)1<<p) p++;
p--;
return min(anc[jos][p].min,find_nec_min(anc[jos][p].anc,sus));
}

long int find_necc(long int x, long int y)
{
long int necc=0,lca;
lca=find_lca(min(first[x],first[y]),max(first[x],first[y]),1,chainlen,rad_lca);
if (x==lca) necc=find_nec_min(y,lca);
else if (y==lca) necc=find_nec_min(x,lca);
else necc=min(find_nec_min(x,lca),find_nec_min(y,lca));
return necc;
}

void solve()
{
FILE *g=fopen("atac.out","w");
long int i,zi;
for (i=1;i<=m-p;i++)
	{
	zi=find_necc(xi,yi);
	xi=(a*xi+b*yi)%n+1;
	yi=(c*yi+d*zi)%n+1;
	}
for (i=1;i<=p;i++)
	{
	zi=find_necc(xi,yi);
	xi=(a*xi+b*yi)%n+1;
	yi=(c*yi+d*zi)%n+1;
	scrie(g,zi);
	}
fcloseall();
}

int main()
{
citire();
find_chain(rad);
rad_lca=(NOD_ARBDINT*) malloc (sizeof(NOD_ARBDINT));
(*rad_lca).lca=0;
aloca_arb_dint(1,chainlen,rad_lca);
populate_arb_dint();
prepare_nodes();
create_ancestors();
solve();
//print_ad(1,chainlen,rad_lca);
return 0;
}