Cod sursa(job #811245)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 11 noiembrie 2012 19:10:33
Problema Mese Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
int n,MAX,cost[100100],sol;
vector <int> G[100100];

inline bool Sortare(int x,int y)
{
	return cost[x]<cost[y];
}

inline void DFS(int x)
{
	vector <int>::iterator it;
	for(it=G[x].begin();it!=G[x].end();it++)
	{
		DFS(*it);
		cost[x]+=cost[*it];
	}
	sort(G[x].begin(),G[x].end(),Sortare);
	it=G[x].end()-1;
	while(cost[x]>MAX)
	{
		cost[x]-=cost[*it];
		sol++;
		it--;
	}
}

int main()
{
	int i,tata;
	ifstream fin("mese.in");
	fin>>n>>MAX;
	for(i=1;i<=n;i++)
	{
		fin>>tata>>cost[i];
		G[tata].push_back(i);
	}
	fin.close();
	
	sol=1;
	DFS(0);
	
	ofstream fout("mese.out");
	fout<<sol<<"\n";
	fout.close();
	return 0;
}