Cod sursa(job #726790)

Utilizator feelshiftFeelshift feelshift Data 27 martie 2012 15:27:23
Problema Arbore Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
// http://infoarena.ro/problema/arbore
#include <fstream>
#include <vector>
using namespace std;

const int MAXSIZE = 100001;

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

int nodes,ops,sum;
bool gasit;
int money[MAXSIZE];
vector<int> graph[MAXSIZE];

void depthFirst(int node);
void depthFirst2(int node);

int main() 
{
	in >> nodes >> ops;
	
	int from,to;
	for(int i=1;i<nodes;i++) 
	{
		in >> from >> to;
		
		graph[from].push_back(to);
	}
	
	int type = 0,node = 0;
	for(int i=1;i<=ops;i++) 
	{
		in >> type;
		
		if(type == 1)
		{
			in >> node >> sum;
			depthFirst(node);
		}
		else
		{
			in >> sum;
			
			/*bool found = false;
			for(int k=1;k<=nodes;k++)
				if(money[k] == sum)
				{
					out << k << "\n";
					found = true;
					break;
				}*/
			gasit = false;
			depthFirst2(1);
			
			if(!gasit)
				out << "-1\n";
		}
	}
	out.close();
	
	return (0);
}

void depthFirst(int node) 
{
	money[node] += sum;
	
	for(unsigned int i=0;i<graph[node].size();++i)
		depthFirst(graph[node][i]);
}

void depthFirst2(int node) {
	if(gasit || money[node] > sum) return;
	
	if(money[node] == sum) {
		out << node << "\n", gasit = true;
		return;
	}
	
	for(int i=0;i<graph[node].size();i++)
		depthFirst2(graph[node][i]);
}