Cod sursa(job #726776)

Utilizator fhandreiAndrei Hareza fhandrei Data 27 martie 2012 15:17:09
Problema Arbore Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.04 kb
//Include
#include <fstream>
#include <vector>
using namespace std;

//Constante
const int MAX_SIZE = (int)1e5+1;

//Functii
void dfs(int node);

//Variabile
ifstream in("arbore.in");
ofstream out("arbore.out");

int nrNoduri, operatii;
int question;
int start, sum;
int bani[MAX_SIZE];
vector<int> graf[MAX_SIZE];

//Main
int main()
{
	in >> nrNoduri >> operatii;
	int cFrom, cTo;
	for(int i=1 ; i<nrNoduri ; ++i)
	{
		in >> cFrom >> cTo;
		graf[cFrom].push_back(cTo);
	}
	
	while(operatii--)
	{
		in >> question;
		if(question == 1)
		{
			in >> start >> sum;
			dfs(start);
		}
		else
		{
			in >> sum;
			bool gasit = false;
			for(int i=1 ; i<=nrNoduri ; ++i)
				if(bani[i] == sum)
				{
					gasit=true;
					out << i << '\n';
					break;
				}
			if(!gasit)
				out << "-1\n";
		}
	}
	
	in.close();
	out.close();
	return 0;
}

void dfs(int node)
{
	vector<int>::iterator it, end;
	bani[node] += sum;
	end = graf[node].end();
	for(it=graf[node].begin() ; it!=end ; ++it)
		dfs(*it);
}