Cod sursa(job #119057)

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