Cod sursa(job #117167)

Utilizator mihai0110Bivol Mihai mihai0110 Data 20 decembrie 2007 20:54:52
Problema Dosare Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<stdio.h>
FILE *f=fopen("dosare.in","r");
FILE *g=fopen("dosare.out","w");
long n,i,j,x,rez;
long a[334][334];
long v[334],v2[334],nr[334],nrx[334],nrz[334];
void solve(long x)
{
int i;
for(i=1;i<=a[x][0];i++)
if(!v2[a[x][i]])
{
if(i==1) {
nrx[ a[x][i] ]=nrx[x]+1;
}
else
{
nrx[a[x][i]]=nrx[a[x][i-1]]+1;
}
v2[a[x][i]]=1;
solve(a[x][i]);
}
}
int poz(long li,long ls,long X)
{
long aux,i,j;
int t=0;
i=li;
j=ls;
while(i<j)
{
if(nr[a[X][i]]<nr[a[X][j]])
{
aux=a[X][i];
a[X][i]=a[X][j];
a[X][j]=aux;
}
t=1-t;
if(t)
j--;
else
i++;
}
return i;
}
void qs(long li,long ls,long X)
{
int k;
if(li<ls)
{
k=poz(li,ls,X);
qs(li,k-1,X);
qs(ls,k+1,X);
}
}
void precalc(long x)
{
long i;
for(i=1;i<=a[x][0];i++)
if(!v[a[x][i]])
{
v[a[x][i]]=1;
precalc(a[x][i]);
nr[x]+=nr[a[x][i]];
}
}
int main(void)
{
fscanf(f,"%ld",&n);
for(i=2;i<=n;i++)
{
fscanf(f,"%ld",&x);
a[x][0]++;
a[x][a[x][0]]=i;
}
for(i=1;i<=n;i++)
{
fscanf(f,"%ld",&nr[i]);
nrz[i]=nr[i];
}
precalc(1);
i=i;
for(i=1;i<=n;i++)
qs(1,a[i][0],i);
nrx[1]=1;
solve(1);
for(i=1;i<=n;i++)
rez+=nrx[i]*nrz[i];
fprintf(g,"%ld\n",rez);
fclose(f);
fclose(g);
return 0;
}