Cod sursa(job #1412807)

Utilizator Aavatar36Russu Vadim Aavatar36 Data 1 aprilie 2015 16:03:25
Problema Arbore Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
#include <vector>
#include <stack>
std::ifstream fin("arbore.in");
std::ofstream fout("arbore.out");
std::vector<int> v[100010];
int suma[100010];

int main()
{
	int n, m;
	fin >> n >> m;
	std::stack<std::pair<int, int> > coada;
	for (int i = 1; i < n; ++i)
	{
		int a, b;
		fin >> a >> b;
		v[a].push_back(b);
	}
	for (int i = 0; i < m; ++i)
	{
		int t, p, s;
		fin >> t;
		if (t == 1) {
			fin >> p >> s;
			suma[p] += s;
		} else {
			fin >> s;
			coada.push(std::make_pair(1, suma[1]));
			std::pair<int, int> front;
			bool gasit = 0;
			while (!coada.empty()) {
				front = coada.top();
				coada.pop();
				if (front.second == s) {fout << front.first << "\n"; gasit = 1; break;}
				for (std::vector<int>::iterator it = v[front.first].begin(); it != v[front.first].end(); it++)
				{
					if (front.second + suma[*it] <= s) {
						coada.push(std::make_pair(*it, front.second + suma[*it]));
					}
				}
			}
			if (!gasit) {
				fout << "-1\n";
			}
			while(!coada.empty()){
				coada.pop();
			}
		}
	}
	// for (int i = 1; i <= n; ++i)
	// {
	// 	fout << suma[i] << " ";
	// }
	return 0;
}