Cod sursa(job #34534)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 20 martie 2007 21:08:10
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.58 kb
# include <stdio.h>

/////////////////////////////////////
// DECLARATIONS
/////////////////////////////////////

const int MAXN=32000;

typedef struct NODE_TREE {long int cost,ffiu,nfrate;};
NODE_TREE tree[MAXN+1];

long int chain[MAXN*3+3];
long int ccost[MAXN*3+3];
long int chain_crt=0;
long int first[MAXN+1];


long int n,m,p,x,y,a,b,c,d;

/////////////////////////////////////
// INITIAL TREE INTERFACE
/////////////////////////////////////

void update_node_tree(long int tata,long int fiu, long int cost)
{
if (tree[tata].ffiu==0)
	{
	tree[tata].ffiu=fiu;
	tree[fiu].cost=cost;
	}
else
	{
	x=tree[tata].ffiu;
	while (tree[x].nfrate!=0) x=tree[x].nfrate;
	tree[x].nfrate=fiu;
	tree[fiu].cost=cost;
	}
}

/////////////////////////////////////
// SEGMENT TREE
/////////////////////////////////////

long int segtree[3*3*MAXN+3];

long int min(long int a, long int b)
{
if (a==0) return b;
else if (a>b) return b;
return a;
}

long int search_min(long int c, long int stg, long int drt, long int st, long int dr)
{
long int m,s=0;
if (st>=stg&&drt>=dr) return segtree[c];
m=(st+dr)/2;
if (stg<=m) s=search_min(2*c,stg,drt,st,m);
if (drt> m) s=min(s,search_min(2*c+1,stg,drt,m+1,dr));
return s;
}

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

void update_seg_tree(long int drta,long int cost)
{
long int st=1,dr=chain_crt,m=(st+dr)/2,crt=1;
while (crt<=3*chain_crt)
	{
	segtree[crt]=min(segtree[crt],cost);
	m=(st+dr)/2;
	if (drta<=m)
		{
		crt*=2;
		if (dr==m) break;
		dr=m;
		}
	else
		{
		crt*=2;crt++;
		st=m+1;
		}
	}
}

void generate_segment_tree()
{
long int i;
for (i=2;i<=chain_crt;i++)
	update_seg_tree(i,ccost[i]);
}

/////////////////////////////////////
// EULER CHAIN
/////////////////////////////////////

void df (long int nod)
{
chain[++chain_crt]=nod;
if (chain_crt!=1) ccost[chain_crt]=tree[nod].cost;
if (tree[nod].ffiu!=0)
	{
	df(tree[nod].ffiu);
	chain[++chain_crt]=nod;
	ccost[chain_crt]=tree[tree[nod].ffiu].cost;
	long int x=tree[tree[nod].ffiu].nfrate;
	while (x)
		{
		df(x);
		chain[++chain_crt]=nod;
		ccost[chain_crt]=tree[x].cost;
		x=tree[x].nfrate;
		}
	}
}

void euler_chain()
{
df(2);
}

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

/////////////////////////////////////
// MAIN INTERFACE
/////////////////////////////////////

void citire()
{
int sel[MAXN+1]={0};
FILE *f=fopen("atac.in","r");
fscanf(f,"%ld%ld%ld",&n,&m,&p);
long int i,dest,cost;
for (i=2;i<=n;i++)
	{
	fscanf(f,"%ld%ld",&dest,&cost);
	if (sel[i]==0&&sel[dest]==0)
		{
		update_node_tree(i,dest,cost);
		sel[i]=sel[dest]=1;
		}
	else if (sel[i]==1)
		{
		update_node_tree(i,dest,cost);
		sel[dest]=1;
		}
	else
		{
		update_node_tree(dest,i,cost);
		sel[i]=1;
		}
	}
fscanf(f,"%ld%ld%ld%ld%ld%ld",&x,&y,&a,&b,&c,&d);
fclose(f);
}

void scrie()
{
FILE *g=fopen("atac.out","w");
long int xp=x,yp=y,nec,i,xx,yy;
for (i=1;i<=m-p;i++)
	{
	if (xp==yp) nec=0;
	else
		{
		xx=min(first[xp]+1,first[yp]);
		yy=max(first[xp]+1,first[yp]);
		nec=search_min(1,xx,yy,1,chain_crt);
		}
	xp=(xp*a+yp*b)%n+1;
	yp=(yp*c+nec*d)%n+1;
	}
for (i=1;i<=p;i++)
	{
	if (xp==yp) nec=0;
	else
		{
		xx=min(first[xp]+1,first[yp]);
		yy=max(first[xp]+1,first[yp]);
		nec=search_min(1,xx,yy,1,chain_crt);
		}
	xp=(xp*a+yp*b)%n+1;
	yp=(yp*c+nec*d)%n+1;
	fprintf(g,"%ld\n",nec);
	}
fcloseall();
}

int main()
{
citire();
euler_chain();
prepare_nodes();
generate_segment_tree();
scrie();
return 0;
}