Source code for submission s991

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. vector<int> children;
  9.  
  10. Node( int n = 0 )
  11. {
  12. num = n;
  13. }
  14.  
  15. void add( int n )
  16. {
  17. children.push_back(n);
  18. }
  19.  
  20. int ccount()
  21. {
  22. return children.size();
  23. }
  24. };
  25.  
  26. int bublej( int ** pole, Node * node, Node ** graph, int parent )
  27. {
  28. if( node->ccount() == 1 )
  29. {
  30. //printf( "jsem %d a vracim %d\n", node->num, node->effort );
  31. return pole[parent-1][node->num-1];
  32. }
  33.  
  34. int tmp = pole[parent-1][node->num-1];
  35. //printf( "jsem %d a prisel jsem z %d\n", node->num, parent );
  36.  
  37. int sum = 0;
  38. for( int i = 0; i < node->ccount(); i++ )
  39. {
  40. if( node->children[i] == parent )
  41. continue;
  42.  
  43. int b = bublej( pole, graph[ node->children[i]-1 ], graph, node->num );
  44.  
  45. //printf( "sum (%d) += %d\n", sum, b );
  46. sum += b;
  47. }
  48.  
  49. //printf( "jsem %d, mam %d a od deti mam %d\n", node->num, node->effort, sum );
  50. if( sum < tmp )
  51. tmp = sum;
  52.  
  53. pole[parent-1][node->num-1] = tmp;
  54. pole[node->num-1][parent-1] = tmp;
  55. return tmp;
  56. }
  57.  
  58. int main()
  59. {
  60. int ** pole = new int* [1000];
  61. for( int i = 0; i < 1000; i++ )
  62. pole[i] = new int[1000];
  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. pole[center-1][center-1] = 2000;
  72. for( int i = 0; i < nodec-1; i++ )
  73. {
  74. int n,c,e;
  75. scanf( "%d %d %d\n", &n,&c,&e );
  76.  
  77. nodeArr[n-1]->add(c);
  78. nodeArr[c-1]->add(n);
  79. pole[n-1][c-1] = e;
  80. pole[c-1][n-1] = e;
  81. }
  82.  
  83. /*
  84. for( int i = 0; i < nodec; i++ )
  85. {
  86. printf( "Node%d (%d) : ", nodeArr[i]->num, nodeArr[i]->effort );
  87. for( int j = 0; j < nodeArr[i]->ccount(); j++ )
  88. printf( " %d", nodeArr[i]->children[j] );
  89. printf( "\n" );
  90. }
  91. */
  92.  
  93. int result = bublej( pole, nodeArr[center-1], nodeArr, center );
  94. printf( "%d\n", result );
  95. }
  96.  
  97. return 0;
  98. }
  99.  

Diff to submission s957

fr.cpp

--- c5.s957.cteam031.fr.cpp.0.fr.cpp
+++ c5.s991.cteam031.fr.cpp.0.fr.cpp
@@ -6,13 +6,9 @@
 {
         int num;
-        int effort;
-        int min;
         vector<int> children;
-        int parent;
         
-        Node( int n = 0, int p = 0 )
+        Node( int n = 0 )
         {
                 num = n;
-                parent = p;
         }
         
@@ -62,4 +58,8 @@
 int main()
 {
+        int ** pole = new int* [1000];
+        for( int i = 0; i < 1000; i++ ) 
+                pole[i] = new int[1000];
+                
         int nodec, center;
         while( scanf("%d %d\n", &nodec, &center) == 2 )
@@ -68,10 +68,6 @@
                 for( int i = 0; i < nodec; i++ )
                         nodeArr[i] = new Node(i+1);
-                        
-                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++ )
                 {
@@ -79,9 +75,4 @@
                         scanf( "%d %d %d\n", &n,&c,&e );
                         
-                        if( c != center )
-                                nodeArr[c-1]->effort = e;
-                        else
-                                nodeArr[n-1]->effort = e;
-                        
                         nodeArr[n-1]->add(c);
                         nodeArr[c-1]->add(n);