Cod sursa(job #1645444)

Utilizator LegionHagiu Stefan Legion Data 10 martie 2016 12:22:11
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<long long,long long> > fii[16001];
long long costsubarbore[16001];
long long cost[16001];
long long total;
bool cmp(pair<long long,long long> a,pair<long long,long long> b)
{
    if (a.second>=b.second)
    {
        return true;
    }
    return false;
}
long long calc(long long k)
{
    long long i;
    long long costcurent;
    if (fii[k].empty())
    {
        return cost[k];
    }
    else
    {
        for (i=0;i<fii[k].size();i++)
        {
            fii[k][i].second=calc(fii[k][i].first);
        }
        sort(fii[k].begin(),fii[k].end(),cmp);
        costcurent=cost[k];
        for (i=0;i<fii[k].size();i++)
        {
            costcurent+=fii[k][i].second;
        }
        return costcurent;
    }
}
void parcurge(long long k,long long t)
{
    long long i;
    total+=cost[k]*t;
    for (i=0;i<fii[k].size();i++)
    {
        parcurge(fii[k][i].first,t+i+1);
    }
}
int main()
{
    ifstream in("dosare.in");
    ofstream out("dosare.out");
    long long i,n,x;
    in>>n;
    for (i=2;i<=n;i++)
    {
        in>>x;
        fii[x].push_back(make_pair(i,0));
    }
    for (i=1;i<=n;i++)
    {
        in>>cost[i];
    }
    calc(1);
    parcurge(1,1);
    out<<total;
}