Cod sursa(job #1645240)

Utilizator LegionHagiu Stefan Legion Data 10 martie 2016 11:39:26
Problema Dosare Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int,int> > fii[16001];
int costsubarbore[16001];
int cost[16001];
int total;
bool cmp(pair<int,int> a,pair<int,int> b)
{
	if (a.second>b.second)
	{
		return true;
	}
	return false;
}
int calc(int k)
{
	int i;
	int 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*(i+2);
		}
		return costcurent;
	}
}
void parcurge(int k,int t)
{
	int 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");
    int 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;
}