Source code for submission s728

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

Diff to submission s676

fr.cpp

--- c5.s676.cteam021.fr.cpp.0.fr.cpp
+++ c5.s728.cteam021.fr.cpp.0.fr.cpp
@@ -4,6 +4,8 @@
 using namespace std;
 
-int getCountFor ( multimap<int, int> & edges, map<pair<int, int>, int> & values, int X, int prize, int last )
-{
+int getCountFor ( multimap<int, int> & edges, map<pair<int, int>, int> & values, int X, int last )
+{       
+        int prize = values[ pair<int, int>( X, last ) ];
+
         multimap<int, int>::iterator from = edges.lower_bound( X );
         multimap<int, int>::iterator to = edges.upper_bound( X );
@@ -11,11 +13,13 @@
         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 );
+                        x++;
+                        sum += getCountFor( edges, values, from->second, X );
                 }
         }
         
-        if ( x <= 1 ) { return prize; }
+        if (x == 0) {
+                return prize;
+        }
         
         return prize > sum ? sum : prize;
@@ -29,4 +33,6 @@
                 multimap<int, int> edges;
                 map<pair<int, int>, int> values;
+                
+                values[pair<int, int>(C, C)] = 10000;
 
                 int U, V, W;
@@ -39,5 +45,4 @@
                         edges.insert(p1);
                         edges.insert(p2);
-        
                         
                         values[ p1 ] = W;
@@ -45,5 +50,5 @@
                 }
                 
-                cout << getCountFor(edges, values, C, 10000, C ) << endl;
+                cout << getCountFor(edges, values, C, C) << endl;
         }