Cod sursa(job #274286)

Utilizator FlorianFlorian Marcu Florian Data 9 martie 2009 16:38:49
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<stdio.h>
#include<stdlib.h>
#define Nmax 16003
#define ll long long
FILE*f=fopen("dosare.in","r");
FILE*g=fopen("dosare.out","w");
struct Graf
 {
   int vf;
   Graf *urm;
 };
ll acces[Nmax]; // de cate ori accesez dosarul i
ll cst;
int n;
Graf *G[Nmax];
inline void ins(int x, int y) // x este parintele lui y
 {
  Graf *q=new Graf;
  q->vf = y;
  q->urm = G[x];
  G[x] = q;
 }
inline int cmp(const void*a, const void*b)
 {
  return *(int*)b-*(int*)a;
 }
void read()
 {
  fscanf(f,"%d",&n);
  int i;
  for(i=2;i<=n;++i)
   {
    int x,y;
    fscanf(f,"%d",&x);
    ins(x,i);
   }
  for(i=1;i<=n;++i) fscanf(f,"%lld",&acces[i]);
 }
void dfs(int x)
 {
  Graf *q;
  ll sol[Nmax],p=0,ok=0;
  for(q=G[x];q;q=q->urm)
   {
    dfs(q->vf);
    ok=1;
    sol[p++] = acces[q->vf];
    acces[x] += acces[q->vf];
   }
  if(ok)
   {
     qsort(sol,p, sizeof(sol[0]), cmp);
     int i;
     for(i=0;i<p;++i) cst += sol[i] * (i+1);
   }
 }
int main()
 {
  read();
  dfs(1);
  cst+=acces[1];
  fprintf(g,"%lld\n",cst);
  return 0;
 }