Source code for submission s676

Go to diff to previous submission

fr.cpp

  1. #include <iostream>
  2. #include <map>
  3.  
  4. using namespace std;
  5.  
  6. int getCountFor ( multimap<int, int> & edges, map<pair<int, int>, int> & values, int X, int prize, int last )
  7. {
  8. multimap<int, int>::iterator from = edges.lower_bound( X );
  9. multimap<int, int>::iterator to = edges.upper_bound( X );
  10.  
  11. int sum = 0; int x = 0;
  12. for ( ; from != to; ++from ) {
  13. x++;
  14. if ( from->second != last ) {
  15. sum += getCountFor( edges, values, from->second, values[ pair<int, int>(X, from->second ) ], X );
  16. }
  17. }
  18.  
  19. if ( x <= 1 ) { return prize; }
  20.  
  21. return prize > sum ? sum : prize;
  22. }
  23.  
  24. int main ( void )
  25. {
  26. int N, C;
  27.  
  28. while ( cin >> N >> C ) {
  29. multimap<int, int> edges;
  30. map<pair<int, int>, int> values;
  31.  
  32. int U, V, W;
  33. for ( int i = 0; i < N - 1; i++ ) {
  34. cin >> U >> V >> W;
  35.  
  36. pair<int, int> p1( U, V );
  37. pair<int, int> p2( V, U );
  38.  
  39. edges.insert(p1);
  40. edges.insert(p2);
  41.  
  42.  
  43. values[ p1 ] = W;
  44. values[ p2 ] = W;
  45. }
  46.  
  47. cout << getCountFor(edges, values, C, 10000, C ) << endl;
  48. }
  49.  
  50. return 0;
  51. }
  52.  
  53.  

Diff to submission s525

fr.cpp

--- c5.s525.cteam021.fr.cpp.0.fr.cpp
+++ c5.s676.cteam021.fr.cpp.0.fr.cpp
@@ -1,37 +1,24 @@
 #include <iostream>
-#include <vector>
 #include <map>
 
 using namespace std;
 
-class CNode
+int getCountFor ( multimap<int, int> & edges, map<pair<int, int>, int> & values, int X, int prize, int last )
 {
-public:
-        vector< CNode*> nexts;
-        int prize;
-        
-        CNode ( int p )
-                : prize( p ) {}
-        
-        void insert ( CNode * toInsert )
-        {
-                nexts.push_back( toInsert );
-        }
+        multimap<int, int>::iterator from = edges.lower_bound( X );
+        multimap<int, int>::iterator to = edges.upper_bound( X );
         
-        int getCount ( void )
-        {
-                int len = nexts.size(), sum = 0;
-                
-                if ( len == 0 ) {
-                        return prize;
-                }
-                
-                for ( int i = 0; i < len; i++ ) {
-                        sum += nexts[ i ]->getCount();
+        int sum = 0; int x = 0;
+        for ( ; from != to; ++from ) {
+                x++;
+                if ( from->second != last ) {
+                        sum += getCountFor( edges, values, from->second, values[ pair<int, int>(X, from->second ) ], X );
                 }
-                
-                return prize > sum ? sum : prize;
         }
-};
+        
+        if ( x <= 1 ) { return prize; }
+        
+        return prize > sum ? sum : prize;
+}
 
 int main ( void )
@@ -40,24 +27,23 @@
 
         while ( cin >> N >> C ) {
-                map<int, CNode* > nodes;
-                
-                nodes[ C ] = new CNode ( 10000 );
+                multimap<int, int> edges;
+                map<pair<int, int>, int> values;
 
-                int U, V, W;    
+                int U, V, W;
                 for ( int i = 0; i < N - 1; i++ ) {
                         cin >> U >> V >> W;
                         
-                        if ( nodes.find(U) == nodes.end() ) {
-                                int tmp = U;
-                                U = V;
-                                V = tmp;                        
-                        }
+                        pair<int, int> p1( U, V );
+                        pair<int, int> p2( V, U );
                         
-                        CNode * n = new CNode ( W );
-                        nodes[ U ] -> insert( n );
-                        nodes[ V ] = n;
+                        edges.insert(p1);
+                        edges.insert(p2);
+        
+                        
+                        values[ p1 ] = W;
+                        values[ p2 ] = W;
                 }
                 
-                cout << nodes[ C ]->getCount() << endl;
+                cout << getCountFor(edges, values, C, 10000, C ) << endl;
         }