Cod sursa(job #119049)

Utilizator hadesgamesTache Alexandru hadesgames Data 29 decembrie 2007 12:34:14
Problema Dosare Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <stdio.h>
#include <stdlib.h>
int a[16001],b[16001],d[16001],e[16000],n;
int *c[16001];
int compare( const void* a, const void* b ) {
   int* arg1 = (int*) a;
   int* arg2 = (int*) b;
   if( d[*arg1] < d[*arg2] ) return 1;
   else if( d[*arg1] == d[*arg2] ) return 0;
   else return -1;
 }  
void acesari(int x,int y)
{
	d[x]+=y;
	if (x!=1)
		acesari(a[x],y);
}
int calc(int x,int y)
{
	int nr=0,i;
	nr=b[x]*(y+1);
	if (e[x]!=0)
		for (i=0;i<e[x];i++)
		{
			nr+=calc(c[x][i],y+i+1);
		}
	return nr;
}
void citire()
{
	FILE *in;
	int i,x;
	in=fopen("dosare.in","r");
	fscanf(in,"%d",&n);
	for (i=2;i<=n;i++)
	{
		fscanf(in,"%d",&a[i]);
		e[a[i]]++;
	}
	fclose(in);
	for (i=1;i<=n;i++)
	{
		c[i]=new int[e[i]];
	}
	in=fopen("dosare.in","r");
	fscanf(in,"%d",&x);
	for (i=1;i<=n;i++)
		e[i]=0;
	for (i=2;i<=n;i++)
	{
		fscanf(in,"%d",&a[i]);
		//e[a[i]]++;
		//c[a[i]][e[a[i]]-1]=i;
		c[a[i]][e[a[i]]++]=i;
	}
	for (i=1;i<=n;i++)
		fscanf(in,"%d",&b[i]);
	fclose(in);
	
}
int main ()
{
	FILE *out;
	int i,nr;
	out=fopen("dosare.out","w");
	citire();
	d[1]=b[1];
	for (i=2;i<=n;i++)
	{
		d[i]+=b[i];
		acesari(a[i],b[i]);
	}
	for (i=1;i<=n;i++)
		if (e[i]!=0)
			qsort(c[i],e[i],sizeof(c[i][0]),compare);
	nr=calc(1,0);
	fprintf(out,"%d\n",nr);
	fclose(out);
	return 0;
	
}