Cod sursa(job #1383541)

Utilizator hrazvanHarsan Razvan hrazvan Data 10 martie 2015 12:56:48
Problema Dosare Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <stdio.h>
#define MAXN 16000
int fr[MAXN], fr2[MAXN], nod[MAXN], next[MAXN], ult[MAXN], v[MAXN];
long long rez;

void prec(int x){
  int poz = ult[x];
  while(poz > -1){
    prec(nod[poz]);
    fr2[x] += fr2[nod[poz]];
    poz = next[poz];
  }
  fr2[x] += fr[x];
}

void qs(int st, int dr){
  int i = st, j = dr, piv = v[(st + dr) / 2], aux;
  while(i <= j){
    while(fr2[v[i]] > fr2[piv])
      i++;
    while(fr2[v[j]] < fr2[piv])
      j--;
    if(i <= j){
      aux = v[i];
      v[i] = v[j];
      v[j] = aux;
      i++;
      j--;
    }
  }
  if(st < j)
    qs(st, j);
  if(i < dr)
    qs(i, dr);
}

void bfs(int p, int k, int dp){
  int poz, dr = dp;
  poz = ult[p];
  while(poz != -1){
    v[dr] = nod[poz];
    dr++;
    poz = next[poz];
  }
  qs(dp, dr - 1);
  int i;
  for(i = dp; i < dr; i++)
    rez += 1LL * (i - dp + 1 + k) * fr[v[i]];
  for(i = dp; i < dr; i++)
    bfs(v[i], k + i - dp + 1, dr);
}

int main(){
  FILE *in = fopen("dosare.in", "r");
  int n, i, x;
  fscanf(in, "%d", &n);
  for(i = 0; i < n; i++)
    ult[i] = -1;
  for(i = 1; i < n; i++){
    fscanf(in, "%d", &x);
    nod[i - 1] = i;
    next[i - 1] = ult[x - 1];
    ult[x - 1] = i - 1;
  }
  for(i = 0; i < n; i++)
    fscanf(in, "%d", &fr[i]);
  fclose(in);
  rez = fr[0];
  prec(0);
  bfs(0, 1, 0);
  FILE *out = fopen("dosare.out", "w");
  fprintf(out, "%lld", rez);
  fclose(out);
  return 0;
}