Cod sursa(job #117080)

Utilizator hadesgamesTache Alexandru hadesgames Data 20 decembrie 2007 17:19:01
Problema Dosare Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <stdio.h>
#include <stdlib.h>
int a[16001],b[16001],c[16001][500],d[16001],e[16000];
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]!=-1)
		for (i=0;i<=e[x];i++)
		{
			nr+=calc(c[x][i],y+i+1);
		}
	return nr;
}
int main ()
{
	FILE *in,*out;
	int i,nr,n;
	in=fopen("dosare.in","r");
	out=fopen("dosare.out","w");
	fscanf(in,"%d",&n);
	for (i=1;i<=n;i++)
		e[i]=-1;
	for (i=2;i<=n;i++)
	{
		fscanf(in,"%d",&a[i]);
		e[a[i]]++;
		c[a[i]][e[a[i]]]=i;
	}
	for (i=1;i<=n;i++)
	{
		fscanf(in,"%d",&b[i]);
	}
	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]!=-1)
			qsort(c[i],e[i]+1,sizeof(c[i][0]),compare);
	nr=calc(1,0);
	fprintf(out,"%d\n",nr);
	fclose(in);
	fclose(out);
	return 0;
	
}