Cod sursa(job #2912203)

Utilizator cezar_titianuTitianu Cezar cezar_titianu Data 7 iulie 2022 12:19:04
Problema Arbore Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <stdio.h>
#include <vector>

struct Nod {
	int s = 0;
	std::vector <int> vecini;
};

std::vector <Nod> noduri;

int DFS (int nod, int par, int s) {
	int maxVal = -2;
	s -= noduri[nod].s;
	if (s == 0) {
		return nod;
	}
	if (s < 0) {
		return -2;
	}
	for (int copil : noduri[nod].vecini) {
		if (copil == par) {
			continue;
		}
		maxVal = std::max(DFS(copil, nod, s), maxVal);
	}
	return maxVal;
}

int main () {
	FILE *fin, *fout;
	int n, m;
	int q, p, nod, s, i;

	fin = fopen("arbore.in", "r");

	fscanf(fin, "%d%d", &n, &m);
	noduri.resize(n);

	for (i = 0; i < n - 1; i++) {
		fscanf(fin, "%d%d", &p, &nod);
		p--, nod--;
		noduri[p].vecini.push_back(nod);
		noduri[nod].vecini.push_back(p);
	}

	fout = fopen("arbore.out", "w");

	for (i = 0; i < m; i++) {
		fscanf(fin, "%d", &q);
		if (q == 1) {
			fscanf(fin, "%d%d", &p, &s);
			p--;
			noduri[p].s += s;
		}
		else {
			fscanf(fin, "%d", &s);
			fprintf(fout, "%d\n", DFS(0, -1, s) + 1);
		}
	}
	fclose(fin);
	fclose(fout);
	return 0;
}