Cod sursa(job #121696)

Utilizator scvalexAlexandru Scvortov scvalex Data 9 ianuarie 2008 15:24:30
Problema Dosare Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

class Tree {
public:
	Tree() :
		m_n(0)
	{
	}
	
	Tree(int n) :
		m_n(n)
	{
	}
	
	int m_n;
	int m_acc;
	vector<Tree*> child;
};

int acc[16001];
vector<Tree> dosare;
int N(0);

int calculeaza(Tree *t, int lvl = 1, int pos = 0) {
	t->m_acc *= lvl;
	t->m_acc += pos;

	for (int i(0); i < (int)t->child.size(); ++i)
		t->m_acc += calculeaza(t->child[i], lvl + 1, i);
	
	return t->m_acc;
}

void afiseaza(Tree *t, int lvl = 1) {
	cout << "\b\b\b----" << t->m_n << ":" << t->m_acc << endl;
	for (int i(0); i < (int)t->child.size(); ++i) {
		cout << " ";
		for (int j(0); j < lvl; ++j)
			cout << "|   ";
		afiseaza(t->child[i], lvl + 1);
	}
}

bool cmp(Tree *a, Tree *b) {
	return a->m_acc > b->m_acc;
}

void afiseaza_ordonat(Tree *t) {
	//cout << t->m_n << ":" << t->m_acc << ": ";
	
	vector<bool> vizitat(t->child.size(), false);
	
	sort(t->child.begin(), t->child.end(), cmp);
	
	//for (int i(0); i < (int)t->child.size(); ++i)
	//	cout << t->child[i]->m_n << " ";
	//cout << endl;
	
	for (int i(0); i < (int)t->child.size(); ++i)
		afiseaza_ordonat(t->child[i]);
}

int calculeaza_cost(Tree *t, int sofar = 1) {
	//cout << t->m_n << " " << sofar << endl;
	int len = sofar * acc[t->m_n];
	
	for (int i(0); i < (int)t->child.size(); ++i) {
		int val = calculeaza_cost(t->child[i], sofar + i + 1);
		
		len += val;
		//cout << "Drum pana la " << t->child[i]->m_n << ": " << val << endl;
	}
	//cout << endl;
	
	return len;
}

int main(int argc, char *argv)
{
	ifstream fin("dosare.in");
	fin >> N;
	dosare.push_back(Tree(-888));	
	for (int i(1); i <= N; ++i)
		dosare.push_back(Tree(i));
	
	int aux;
	for (int i(2); i <= N; ++i) {
		fin >> aux;
		dosare[aux].child.push_back(&dosare[i]);
	}
	for (int i(1); i <= N; ++i) {
		fin >> dosare[i].m_acc;
		acc[i] = dosare[i].m_acc;
	}
	fin.close();
	
	calculeaza(&dosare[1]);
	
	afiseaza_ordonat(&dosare[1]); // Prelucreaza date. NU STERGE
	
	//afiseaza(&dosare[1]);
	
	ofstream fout("dosare.out");
	fout << calculeaza_cost(&dosare[1]) << endl;
	fout.close();
	
	return 0;
}