C++ - Zadatak Dzeparac - rjesenje

/*

Zimske radionice 2013 - C++ - završni ispit za polaznike

Zadatak: Džeparac

Datum: 2013-01-12

Autor: Kristijan Burnik, udruga informatičara Božo Težak

Gmail: kristijanburnik

Test primjer:

ULAZ:
10
ivica 200 ante
marica 250 ante
slaven 150 ante
pero 220 ivica
marko 190 ivica
barbara 300 ivica
karlo 180 marica
tomislav 190 marica
darko 100 pero
ante 100 rudi

IZLAZ:
100 600 1080 100

*/

#include <iostream>
#include <cstdlib>
#include <map>
#include <vector>
#include <set>

using namespace std;

vector <int> rezultati;
map < string, map<string,int> > stablo;
typedef map<string,int>::iterator IT;


// pridodaj na ukupan dzeparac neke generacije
void dodajRezultat(int generacija , int dzeparac ){
    if (generacija >= rezultati.size() ) {
        rezultati.resize( generacija + 1 );
    }

    rezultati[ generacija ] += dzeparac;
}

// preorder obilazak stabla
void obilazak( string roditelj , int dzeparac = 0 , int generacija = 0 ) {

    // zbroji rezultat na generaciju ( obradi cvor)
    dodajRezultat( generacija , dzeparac  );

    // obidji svu djecu
    if (stablo.count( roditelj )) {

        map<string,int> djeca = stablo[ roditelj ];

        for (IT it = djeca.begin(); it != djeca.end(); it++) {
            obilazak( it->first, it->second , generacija+1 );
        }
    }
}


int main() {

    int n;
    cin >> n;

    // ulazni redak
    string dijete;
    int dzeparac;
    string roditelj;

    // ove dvije strukture koristimo kako bi pronasli korijen
    set<string> skup_djece;
    vector<string> roditelji;


    for (int i = 0 ; i < n; i++) {

        cin >> dijete >> dzeparac >> roditelj;

        // gradi stablo
        stablo[roditelj][dijete] = dzeparac;

        // ove dvije strukture koristimo kako bi pronasli korijen
        skup_djece.insert(dijete);
        roditelji.push_back( roditelj );
    }

    // pronadji korijen
    string korijen;
    for (int i = 0 ; i < roditelji.size(); i++) {
        if (!skup_djece.count(roditelji[i]))
            korijen = roditelji[i];
    }


    // obidji citavo stablo i izracunaj dzeparac svake generacije
    obilazak( korijen );

    // ispisi dzeparac za svaku generaciju pocevsi od prve
    // globalni vector "rezultati" je popunio obilazak
    for (int i = 1 ; i < rezultati.size(); i++) {
        cout << rezultati[i] << " ";
    }

    cout << endl;


    system("pause");
    return 0;
}