Cod sursa(job #198175)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 9 iulie 2008 12:25:59
Problema Dosare Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
# include <stdio.h>
# include <vector>

using namespace std;

# define FIN "dosare.in"
# define FOUT "dosare.out"
# define MAXN 16001
# define ll long long

ll N,i,len,x,s;
ll A[MAXN];
ll P[MAXN];
vector <ll> dosare[MAXN];   

    ll part(ll poz,ll st,ll dr)
    {
        ll i,j,s,aux;
        i = st;
        j = dr;
        s = -1;
        while (i < j)
          {
              if (A[dosare[poz][i]]<A[dosare[poz][j]])
                {
                   aux = dosare[poz][i];
                   dosare[poz][i] = dosare[poz][j];
                   dosare[poz][j] = aux;
                   s = -s;
                }
              if (s == 1) i++;
                     else j--;
          }
        return i;
    }

    void qsort(ll poz,ll st,ll dr)
    {
         ll p;
         if (st<dr)
           {
               p = part(poz,st,dr);
               qsort(poz,st,p-1);
               qsort(poz,p+1,dr);
           }
    }

    int main()
    {
        freopen(FIN,"r",stdin);
        freopen(FOUT,"w",stdout);
        
        scanf("%lld",&N);
        
        for (i = 2; i <= N; ++i)
          {
               scanf("%lld",&x);
               dosare[x].push_back(i);
          }
          
        for (i = 1; i <= N; ++i)
          scanf("%lld",&A[i]);
        
        ll j;  
        for (i = N; i >= 1; i--)
          if (dosare[i].size() != 0)
            {
                len = dosare[i].size() - 1;
                qsort(i,0,len);
                for (j = 0; j <= len; ++j)
                  A[i] += A[dosare[i][j]];
            }
          
        for (i = 1; i <= N; i++)
          if (dosare[i].size() != 0)
            {
                len = dosare[i].size() - 1;
                for (j = 0; j <= len; ++j)
                  A[i] -= A[dosare[i][j]];
            }
        P[1] = 1;
        s = 1*A[1];
        for (i = 1; i <= N; ++i)
          if (dosare[i].size() != 0)
            {
                len = dosare[i].size() - 1;
                for (j = 0; j <= len; ++j)
                  {
                       P[dosare[i][j]] = P[i] + j + 1;
                       s = s + P[dosare[i][j]]*A[dosare[i][j]];
                  }
            }
        
        printf("%lld",s);
                  
        return 0;
    }