Source code for submission s957

Go to diff to previous submission

fr.cpp

  1. #include <cstdio>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. struct Node
  6. {
  7. int num;
  8. int effort;
  9. int min;
  10. vector<int> children;
  11. int parent;
  12.  
  13. Node( int n = 0, int p = 0 )
  14. {
  15. num = n;
  16. parent = p;
  17. }
  18.  
  19. void add( int n )
  20. {
  21. children.push_back(n);
  22. }
  23.  
  24. int ccount()
  25. {
  26. return children.size();
  27. }
  28. };
  29.  
  30. int bublej( int ** pole, Node * node, Node ** graph, int parent )
  31. {
  32. if( node->ccount() == 1 )
  33. {
  34. //printf( "jsem %d a vracim %d\n", node->num, node->effort );
  35. return pole[parent-1][node->num-1];
  36. }
  37.  
  38. int tmp = pole[parent-1][node->num-1];
  39. //printf( "jsem %d a prisel jsem z %d\n", node->num, parent );
  40.  
  41. int sum = 0;
  42. for( int i = 0; i < node->ccount(); i++ )
  43. {
  44. if( node->children[i] == parent )
  45. continue;
  46.  
  47. int b = bublej( pole, graph[ node->children[i]-1 ], graph, node->num );
  48.  
  49. //printf( "sum (%d) += %d\n", sum, b );
  50. sum += b;
  51. }
  52.  
  53. //printf( "jsem %d, mam %d a od deti mam %d\n", node->num, node->effort, sum );
  54. if( sum < tmp )
  55. tmp = sum;
  56.  
  57. pole[parent-1][node->num-1] = tmp;
  58. pole[node->num-1][parent-1] = tmp;
  59. return tmp;
  60. }
  61.  
  62. int main()
  63. {
  64. int nodec, center;
  65. while( scanf("%d %d\n", &nodec, &center) == 2 )
  66. {
  67. Node ** nodeArr = new Node*[nodec];
  68. for( int i = 0; i < nodec; i++ )
  69. nodeArr[i] = new Node(i+1);
  70.  
  71. int ** pole = new int* [nodec];
  72. for( int i = 0; i < nodec; i++ ) pole[i] = new int[nodec];
  73.  
  74. pole[center-1][center-1] = 2000;
  75. nodeArr[center-1]->effort = 2000;
  76. for( int i = 0; i < nodec-1; i++ )
  77. {
  78. int n,c,e;
  79. scanf( "%d %d %d\n", &n,&c,&e );
  80.  
  81. if( c != center )
  82. nodeArr[c-1]->effort = e;
  83. else
  84. nodeArr[n-1]->effort = e;
  85.  
  86. nodeArr[n-1]->add(c);
  87. nodeArr[c-1]->add(n);
  88. pole[n-1][c-1] = e;
  89. pole[c-1][n-1] = e;
  90. }
  91.  
  92. /*
  93. for( int i = 0; i < nodec; i++ )
  94. {
  95. printf( "Node%d (%d) : ", nodeArr[i]->num, nodeArr[i]->effort );
  96. for( int j = 0; j < nodeArr[i]->ccount(); j++ )
  97. printf( " %d", nodeArr[i]->children[j] );
  98. printf( "\n" );
  99. }
  100. */
  101.  
  102. int result = bublej( pole, nodeArr[center-1], nodeArr, center );
  103. printf( "%d\n", result );
  104. }
  105.  
  106. return 0;
  107. }
  108.  

Diff to submission s843

fr.cpp

--- c5.s843.cteam031.fr.cpp.0.fr.cpp
+++ c5.s957.cteam031.fr.cpp.0.fr.cpp
@@ -28,12 +28,13 @@
 };
 
-int bublej( Node * node, Node ** graph, int parent )
+int bublej( int ** pole, Node * node, Node ** graph, int parent )
 {
         if( node->ccount() == 1 )
         {
                 //printf( "jsem %d a vracim %d\n", node->num, node->effort );
-                return node->effort;
+                return pole[parent-1][node->num-1];
         }
         
+        int tmp = pole[parent-1][node->num-1];
         //printf( "jsem %d a prisel jsem z %d\n", node->num, parent );
         
@@ -44,5 +45,5 @@
                         continue;
                 
-                int b = bublej( graph[ node->children[i]-1 ], graph, node->num );
+                int b = bublej( pole, graph[ node->children[i]-1 ], graph, node->num );
                 
                 //printf( "sum (%d) += %d\n", sum, b );
@@ -51,8 +52,10 @@
                 
         //printf( "jsem %d, mam %d a od deti mam %d\n", node->num, node->effort, sum );
-        if( sum < node->effort )
-                node->effort = sum;
+        if( sum < tmp )
+                tmp = sum;
                 
-        return node->effort;
+        pole[parent-1][node->num-1] = tmp;
+        pole[node->num-1][parent-1] = tmp;
+        return tmp;
 }
 
@@ -66,6 +69,9 @@
                         nodeArr[i] = new Node(i+1);
                         
-                nodeArr[center-1]->effort = 2000;
+                int ** pole = new int* [nodec];
+                for( int i = 0; i < nodec; i++ ) pole[i] = new int[nodec];
                 
+                pole[center-1][center-1] = 2000;
+                nodeArr[center-1]->effort = 2000;
                 for( int i = 0; i < nodec-1; i++ )
                 {
@@ -80,4 +86,6 @@
                         nodeArr[n-1]->add(c);
                         nodeArr[c-1]->add(n);
+                        pole[n-1][c-1] = e;
+                        pole[c-1][n-1] = e;
                 }
                 
@@ -92,5 +100,5 @@
                 */
                 
-                int result = bublej( nodeArr[center-1], nodeArr, 0 );
+                int result = bublej( pole, nodeArr[center-1], nodeArr, center );
                 printf( "%d\n", result );
         }