kburnik

C++ - Zadatak Dzeparac - rjesenje

Jan 12th, 2013
107
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  
  3. Zimske radionice 2013 - C++ - završni ispit za polaznike
  4.  
  5. Zadatak: Džeparac
  6.  
  7. Datum: 2013-01-12
  8.  
  9. Autor: Kristijan Burnik, udruga informatičara Božo Težak
  10.  
  11. Gmail: kristijanburnik
  12.  
  13. Test primjer:
  14.    
  15. ULAZ:
  16. 10
  17. ivica 200 ante
  18. marica 250 ante
  19. slaven 150 ante
  20. pero 220 ivica
  21. marko 190 ivica
  22. barbara 300 ivica
  23. karlo 180 marica
  24. tomislav 190 marica
  25. darko 100 pero
  26. ante 100 rudi
  27.  
  28. IZLAZ:
  29. 100 600 1080 100
  30.  
  31. */
  32.  
  33. #include <iostream>
  34. #include <cstdlib>
  35. #include <map>
  36. #include <vector>
  37. #include <set>
  38.  
  39. using namespace std;
  40.  
  41. vector <int> rezultati;
  42. map < string, map<string,int> > stablo;
  43. typedef map<string,int>::iterator IT;
  44.  
  45.  
  46. // pridodaj na ukupan dzeparac neke generacije
  47. void dodajRezultat(int generacija , int dzeparac ){
  48.     if (generacija >= rezultati.size() ) {
  49.         rezultati.resize( generacija + 1 );  
  50.     }
  51.          
  52.     rezultati[ generacija ] += dzeparac;
  53. }
  54.  
  55. // preorder obilazak stabla
  56. void obilazak( string roditelj , int dzeparac = 0 , int generacija = 0 ) {
  57.  
  58.     // zbroji rezultat na generaciju ( obradi cvor)
  59.     dodajRezultat( generacija , dzeparac  );
  60.    
  61.     // obidji svu djecu
  62.     if (stablo.count( roditelj )) {
  63.  
  64.         map<string,int> djeca = stablo[ roditelj ];
  65.        
  66.         for (IT it = djeca.begin(); it != djeca.end(); it++) {
  67.             obilazak( it->first, it->second , generacija+1 );
  68.         }
  69.     }
  70. }
  71.  
  72.  
  73. int main() {
  74.    
  75.     int n;
  76.     cin >> n;
  77.  
  78.     // ulazni redak    
  79.     string dijete;
  80.     int dzeparac;
  81.     string roditelj;
  82.  
  83.     // ove dvije strukture koristimo kako bi pronasli korijen
  84.     set<string> skup_djece;
  85.     vector<string> roditelji;
  86.    
  87.    
  88.     for (int i = 0 ; i < n; i++) {
  89.        
  90.         cin >> dijete >> dzeparac >> roditelj;
  91.    
  92.         // gradi stablo    
  93.         stablo[roditelj][dijete] = dzeparac;
  94.  
  95.         // ove dvije strukture koristimo kako bi pronasli korijen
  96.         skup_djece.insert(dijete);        
  97.         roditelji.push_back( roditelj );
  98.     }
  99.    
  100.     // pronadji korijen
  101.     string korijen;    
  102.     for (int i = 0 ; i < roditelji.size(); i++) {
  103.         if (!skup_djece.count(roditelji[i]))
  104.             korijen = roditelji[i];
  105.     }
  106.    
  107.  
  108.     // obidji citavo stablo i izracunaj dzeparac svake generacije    
  109.     obilazak( korijen );
  110.    
  111.     // ispisi dzeparac za svaku generaciju pocevsi od prve
  112.     // globalni vector "rezultati" je popunio obilazak
  113.     for (int i = 1 ; i < rezultati.size(); i++) {
  114.         cout << rezultati[i] << " ";
  115.     }
  116.    
  117.     cout << endl;
  118.    
  119.    
  120.     system("pause");    
  121.     return 0;
  122. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×