Source code for submission s865

Go to diff to previous submission

fr.cpp

  1. //
  2. // File: fr.cc
  3. // Author: cteam030
  4. //
  5. // Created on October 19, 2013, 12:07 PM
  6. //
  7.  
  8. #include <stdlib.h>
  9. #include <iostream>
  10. #include <string>
  11. #include <vector>
  12.  
  13. using namespace std;
  14.  
  15. //
  16. //
  17. //
  18.  
  19. struct Node {
  20. //int id;
  21. int child;
  22. int effort;
  23. };
  24.  
  25. int getEffort(vector<Node> nodes[], int id);
  26.  
  27. vector<bool> banned_ids;
  28.  
  29. int main(int argc, char** argv) {
  30.  
  31. size_t n, cent;
  32.  
  33. while(cin >> n >> cent) {
  34. //Node nodes[n+1];
  35. vector<Node> nodes[n+1];
  36. for(size_t i = 1;i<n;i++) {
  37. int id,id2,eff;
  38. cin >> id >> id2 >> eff;
  39. Node n1, n2;
  40. n1.child = id2;
  41. n2.child = id;
  42. n1.effort = eff;
  43. n2.effort = eff;
  44.  
  45. nodes[id].push_back(n1);
  46. nodes[id2].push_back(n2);
  47. banned_ids.push_back(false);
  48. }
  49. banned_ids.push_back(false);
  50. banned_ids.push_back(false);
  51.  
  52.  
  53.  
  54. /////////////////////////
  55. int res = 0;
  56. /*for(size_t i=0; i<nodes[cent].subNodes.size(); i++) {
  57.   res += getEffort(nodes, nodes[cent].subNodes[i]);
  58.   }*/
  59.  
  60. for(size_t i=0; i<nodes[cent].size(); i++) {
  61. banned_ids[cent] = true;
  62. res += getEffort(nodes, nodes[cent][i].child);
  63. }
  64.  
  65. cout << res << "\n";
  66. }
  67.  
  68. return (0);
  69. }
  70.  
  71. int getEffort(vector<Node> nodes[], int id) {
  72. int effort = -1;
  73. bool no_child = true;
  74. banned_ids[id] = true;
  75. if(nodes[id].size() <= 1){
  76. return nodes[id][0].effort;
  77. }
  78. int res = 0;
  79. for(size_t i=0; i<nodes[id].size(); i++) {
  80. if(!banned_ids[nodes[id][i].child]) {
  81. res += getEffort(nodes, nodes[id][i].child);
  82. no_child = false;
  83. }else{
  84. effort = nodes[id][i].effort;
  85. }
  86. }
  87. //cout << res << effort
  88. if(res < effort && !no_child)
  89. return res;
  90. else
  91. return effort;
  92. }
  93.  
  94.  

Diff to submission s848

fr.cpp

--- c5.s848.cteam030.fr.cpp.0.fr.cpp
+++ c5.s865.cteam030.fr.cpp.0.fr.cpp
@@ -23,5 +23,5 @@
 };
 
-int getEffort(vector<Node> nodes[], int id, int effort);
+int getEffort(vector<Node> nodes[], int id);
 
 vector<bool> banned_ids;
@@ -60,5 +60,5 @@
         for(size_t i=0; i<nodes[cent].size(); i++) {
             banned_ids[cent] = true;
-            res += getEffort(nodes, nodes[cent][i].child, nodes[cent][i].effort);
+            res += getEffort(nodes, nodes[cent][i].child);
         }
         
@@ -69,5 +69,7 @@
 }
 
-int getEffort(vector<Node> nodes[], int id, int effort) {
+int getEffort(vector<Node> nodes[], int id) {
+    int effort = -1;
+    bool no_child = true;
     banned_ids[id] = true;
     if(nodes[id].size() <= 1){
@@ -76,11 +78,16 @@
     int res = 0;
     for(size_t i=0; i<nodes[id].size(); i++) {
-        if(!banned_ids[nodes[id][i].child])
-            res += getEffort(nodes, nodes[id][i].child, nodes[id][i].effort);
+        if(!banned_ids[nodes[id][i].child]) {
+            res += getEffort(nodes, nodes[id][i].child);
+            no_child = false;
+        }else{
+            effort = nodes[id][i].effort;
+        }
     }
-    if(res > effort)
-        return effort;
-    else
+    //cout << res << effort
+    if(res < effort && !no_child)
         return res;
+    else
+        return effort;
 }