Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- class Element {
- public:
- int wart;
- Element *lewy, *prawy;
- Element(int v) {
- wart = v;
- lewy = nullptr;
- prawy = nullptr;
- }
- };
- Element* root;
- int licznik=0;
- void insertTree(Element *e, int *tab, int liczba, int rozmiartablicy)
- {
- int lewy = 2 * liczba + 1;
- int prawy = 2 * liczba + 2;
- if (lewy > rozmiartablicy || prawy > rozmiartablicy) return;
- if (e == nullptr)
- {
- Element *elem = new Element(tab[liczba]);
- e = elem;
- }
- if (e->lewy == nullptr && e->prawy == nullptr) {
- if (lewy < rozmiartablicy)
- {
- Element *elem = new Element(tab[lewy]);
- e->lewy = elem;
- }
- if (prawy < rozmiartablicy)
- {
- Element *elem = new Element(tab[prawy]);
- e->prawy = elem;
- }
- }
- insertTree(e->lewy, tab, lewy, rozmiartablicy);
- insertTree(e->prawy, tab, prawy, rozmiartablicy);
- }
- vector <int> fun(Element *aktualny, vector<int> sciezka, int k)
- {
- int suma = 0;
- vector<int> sciezkaL, sciezkaP;
- if (aktualny->prawy != nullptr) { sciezkaP = fun(aktualny->prawy, sciezkaP, k); }
- if (aktualny->lewy != nullptr) { sciezkaL = fun(aktualny->lewy, sciezkaL, k); }
- if (aktualny->wart == k) licznik++;
- if (aktualny != root)sciezka.push_back(aktualny->wart);
- if (aktualny->prawy == nullptr && aktualny->lewy == nullptr) return sciezka;
- for (int i = 0; i < sciezkaL.size(); i++)
- {
- for (int j = 0; j < sciezkaP.size(); j++)
- {
- suma = sciezkaL[i] + sciezkaP[j];
- if (suma == k) licznik++;
- }
- }
- sciezka.insert(sciezka.begin(), sciezkaP.begin(), sciezkaP.end());
- sciezka.insert(sciezka.begin(), sciezkaL.begin(), sciezkaL.end());
- if (aktualny != root)
- {
- for (int i = 0; i < sciezka.size() - 1; i++)
- {
- sciezka[i] += aktualny->wart;
- if (sciezka[i] == k) licznik++;
- if (sciezka[i] >= k)
- {
- sciezka.erase(sciezka.begin() + i);
- i = i - 1;
- }
- }
- }
- delete aktualny;
- return sciezka;
- }
- int main()
- {
- int t, n, k, liczba;
- vector<int> sciezka;
- cin >> t;
- int *tab;
- for (int i = 0; i < t; i++)
- {
- cin >> n >> k;
- tab = new int[n + 1];
- root = new Element(0);
- for (int j = 1; j < n + 1; j++)
- {
- cin >> liczba;
- tab[j] = liczba;
- }
- insertTree(root, tab, 0, n + 1);
- fun(root, sciezka, k);
- cout << licznik << endl;
- delete root;
- delete tab;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement