Source code for submission s620

Go to diff to previous submission

fr.cpp

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <utility>
  6. #include <string>
  7. #include <deque>
  8. #include <list>
  9. #include <map>
  10. #include <queue>
  11. #include <set>
  12. #include <stack>
  13. #include <vector>
  14. using namespace std;
  15. /*
  16. 3 1
  17. 2 1 5
  18. 1 3 4
  19. */
  20.  
  21. //#define debug printf
  22. #define debug blackhole
  23. void blackhole(...) {}
  24.  
  25. #define MAXN 1005
  26. int ADJACENT[MAXN][MAXN];
  27. int ADJACENT_W[MAXN][MAXN];
  28. int ADJ_N[MAXN];
  29. long COST[MAXN];
  30. int V;
  31.  
  32. /*
  33. long RECURSE(long FROM_W, long FROM_V, int v) {
  34. long ss = 0;
  35. if (ADJ_N[v] == 1 && FROM_V == -1) {
  36. return ADJACENT_W[v][0]; // jedina hrana z korenu
  37. }
  38. if (ADJ_N[v] == 1) {
  39. return FROM_W; // list
  40. }
  41. for (int i = 0; i < ADJ_N[v]; i++) {
  42. if (ADJACENT[v][i] == FROM_V) continue;
  43. ss += RECURSE(ADJACENT_W[v][i], v, ADJACENT[v][i]);
  44. }
  45. if (FROM_W != -1 && FROM_W < ss) ss = FROM_W;
  46. return ss;
  47. }
  48. */
  49.  
  50. /*
  51. long FROM_WS[10000], FROM_VS[10000], VS[10000], IS[10000], RESULT;
  52. long STACKSIZE=0;
  53.  
  54. void RECURSE() {
  55. long FROM_W=FROM_WS[STACKSIZE], FROM_V=FROM_VS[STACKSIZE], v=VS[STACKSIZE];
  56. if (ADJ_N[v] == 1) return FROM_W;
  57. for (int i = 0; i < ADJ_N[v]; i++) {
  58. if (ADJACENT[v][i] == FROM_V) continue;
  59. ss += RECURSE(ADJACENT_W[v][i], v, ADJACENT[v][i]);
  60. if (FROM_W != -1 && FROM_W < ss) {
  61. ss = FROM_W; break;
  62. }
  63. }
  64. if (FROM_W != -1 && FROM_W < ss) ss = FROM_W;
  65. return ss;
  66. }
  67. */
  68. int KOR = -1;
  69.  
  70. void DESTROY_ALL_BELOW(int v) {
  71. if (COST[v] != -1) return;
  72. if (ADJ_N[v] == 1 && v != KOR) {
  73. COST[v] = ADJACENT_W[v][0];
  74. debug("list(%d): cost=%d\n", v, ADJACENT_W[v][0]);
  75. return;
  76. }
  77.  
  78. long SUM = 0;
  79. long PATH_UP = -1;
  80. for (int i = 0; i < ADJ_N[v]; i++) {
  81. if (COST[ADJACENT[v][i]] != -1) {
  82. SUM += COST[ADJACENT[v][i]];
  83. } else {
  84. debug("Path up of %d: vertex %d\n", v, ADJACENT[v][i]);
  85. if (PATH_UP != -1) {
  86. printf("ERR"); exit(2);
  87. }
  88. PATH_UP = ADJACENT_W[v][i];
  89. }
  90. }
  91. debug("path up=%ld sum=%ld\n", PATH_UP, SUM);
  92.  
  93. long Q = -1;
  94. if (PATH_UP == -1 || SUM < PATH_UP) Q = SUM;
  95. else Q = PATH_UP;
  96.  
  97. debug("COST[%d]<-%ld\n", v, Q);
  98. COST[v] = Q;
  99. }
  100.  
  101. long QUEUE[MAXN];
  102. long QZ = 0;
  103. long QL = 0;
  104.  
  105. void GO() {
  106. if (KOR==-1) { printf("ERROR!!!\n"); exit(1); }
  107. debug("KOR=%d\n",KOR);
  108. for (int i=0;i<MAXN;i++) {
  109. ADJ_N[i]=0;
  110. COST[i] = -1;
  111. }
  112. for (int i = 0; i < V - 1; i++) {
  113. int a, b, weight;
  114. scanf("%d%d%d", &a, &b, &weight);
  115. //printf("%d %d %d\n", a,b,weight);
  116. //printf("%d %d\n", ADJ_N[a], ADJ_N[b]);
  117. ADJACENT[a][ADJ_N[a]] = b;
  118. ADJACENT_W[a][ADJ_N[a]] = weight;
  119. ADJ_N[a]++;
  120. ADJACENT[b][ADJ_N[b]] = a;
  121. ADJACENT_W[b][ADJ_N[b]] = weight;
  122. ADJ_N[b]++;
  123. }
  124.  
  125. QZ=0;
  126. for (int i = 0; i < V + 1; i++) {
  127. if (ADJ_N[i] == 1 && i != KOR) {
  128. QUEUE[QL++] = i;
  129. debug("LIST: %d\n", i);
  130. }
  131. }
  132.  
  133. while (QZ<QL) {
  134. DESTROY_ALL_BELOW(QUEUE[QZ]);
  135. for (int i = 0; i < ADJ_N[QUEUE[QZ]]; i++) {
  136. if (COST[ADJACENT[QUEUE[QZ]][i]] == -1) {
  137. QUEUE[QL++] = ADJACENT[QUEUE[QZ]][i];
  138. }
  139. }
  140. QZ++;
  141. }
  142.  
  143. printf("%ld\n", COST[KOR]);
  144.  
  145. // printf("%ld\n", RECURSE(-1, -1, KOR));
  146. }
  147.  
  148. int main() {
  149. while (true) {
  150. if (scanf("%d%d", &V, &KOR) != 2) break;
  151. GO();
  152. }
  153. return 0;
  154. }
  155.  

Diff to submission s512

fr.cpp

--- c5.s512.cteam032.fr.cpp.0.fr.cpp
+++ c5.s620.cteam032.fr.cpp.0.fr.cpp
@@ -13,16 +13,45 @@
 #include <vector>
 using namespace std;
+/*
+3 1
+2 1 5
+1 3 4 
+*/
 
-#define debug printf
-//#define debug blackhole
+//#define debug printf
+#define debug blackhole
 void blackhole(...) {}
 
-int ADJACENT[2000][2000];
-int ADJACENT_W[2000][2000];
-int ADJ_N[2000];
+#define MAXN 1005
+int ADJACENT[MAXN][MAXN];
+int ADJACENT_W[MAXN][MAXN];
+int ADJ_N[MAXN];
+long COST[MAXN];
 int V;
 
+/*
 long RECURSE(long FROM_W, long FROM_V, int v) {
         long ss = 0;
+        if (ADJ_N[v] == 1 && FROM_V == -1) {
+                return ADJACENT_W[v][0]; // jedina hrana z korenu
+        }
+        if (ADJ_N[v] == 1) {
+                return FROM_W; // list
+        }
+        for (int i = 0; i < ADJ_N[v]; i++) {
+                if (ADJACENT[v][i] == FROM_V) continue;
+                ss += RECURSE(ADJACENT_W[v][i], v, ADJACENT[v][i]);
+        }
+        if (FROM_W != -1 && FROM_W < ss) ss = FROM_W;
+        return ss;
+}
+*/
+
+/*
+long FROM_WS[10000], FROM_VS[10000], VS[10000], IS[10000], RESULT;
+long STACKSIZE=0;
+
+void RECURSE() {
+        long FROM_W=FROM_WS[STACKSIZE], FROM_V=FROM_VS[STACKSIZE], v=VS[STACKSIZE];
         if (ADJ_N[v] == 1) return FROM_W;
         for (int i = 0; i < ADJ_N[v]; i++) {
@@ -36,26 +65,89 @@
         return ss;
 }
+*/
+int KOR = -1;
 
-void GO(int KOR) {
-        for (int i=0;i<V;i++) {
+void DESTROY_ALL_BELOW(int v) {
+        if (COST[v] != -1) return;
+        if (ADJ_N[v] == 1 && v != KOR) {
+                COST[v] = ADJACENT_W[v][0];
+                debug("list(%d): cost=%d\n", v, ADJACENT_W[v][0]);
+                return;
+        }
+
+        long SUM = 0;
+        long PATH_UP = -1;
+        for (int i = 0; i < ADJ_N[v]; i++) {
+                if (COST[ADJACENT[v][i]] != -1) {
+                        SUM += COST[ADJACENT[v][i]];
+                } else {
+                        debug("Path up of %d: vertex %d\n", v, ADJACENT[v][i]);
+                        if (PATH_UP != -1) {
+                                printf("ERR"); exit(2);
+                        }
+                        PATH_UP = ADJACENT_W[v][i];
+                }
+        }
+        debug("path up=%ld sum=%ld\n", PATH_UP, SUM);
+
+        long Q = -1;
+        if (PATH_UP == -1 || SUM < PATH_UP) Q = SUM;
+        else Q = PATH_UP;
+
+        debug("COST[%d]<-%ld\n", v, Q);
+        COST[v] = Q;
+}
+
+long QUEUE[MAXN];
+long QZ = 0;
+long QL = 0;
+
+void GO() {
+        if (KOR==-1) { printf("ERROR!!!\n"); exit(1); }
+        debug("KOR=%d\n",KOR);
+        for (int i=0;i<MAXN;i++) {
                 ADJ_N[i]=0;
+                COST[i] = -1;
         }
         for (int i = 0; i < V - 1; i++) {
                 int a, b, weight;
                 scanf("%d%d%d", &a, &b, &weight);
+                //printf("%d %d %d\n", a,b,weight);
+                //printf("%d %d\n", ADJ_N[a], ADJ_N[b]);
                 ADJACENT[a][ADJ_N[a]] = b;
-                ADJACENT_W[a][ADJ_N[a]++] = weight;
+                ADJACENT_W[a][ADJ_N[a]] = weight;
+                ADJ_N[a]++;
                 ADJACENT[b][ADJ_N[b]] = a;
-                ADJACENT_W[b][ADJ_N[b]++] = weight;
+                ADJACENT_W[b][ADJ_N[b]] = weight;
+                ADJ_N[b]++;
         }
 
-        printf("%ld\n", RECURSE(-1, -1, KOR));
+        QZ=0;
+        for (int i = 0; i < V + 1; i++) {
+                if (ADJ_N[i] == 1 && i != KOR) {
+                        QUEUE[QL++] = i;
+                        debug("LIST: %d\n", i);
+                }
+        }
+
+        while (QZ<QL) {
+                DESTROY_ALL_BELOW(QUEUE[QZ]);
+                for (int i = 0; i < ADJ_N[QUEUE[QZ]]; i++) {
+                        if (COST[ADJACENT[QUEUE[QZ]][i]] == -1) {
+                                QUEUE[QL++] = ADJACENT[QUEUE[QZ]][i];
+                        }
+                }
+                QZ++;
+        }
+
+        printf("%ld\n", COST[KOR]);
+
+        // printf("%ld\n", RECURSE(-1, -1, KOR));
 }
 
 int main() {
         while (true) {
-                int KOR;
                 if (scanf("%d%d", &V, &KOR) != 2) break;
-                GO(KOR);
+                GO();
         }
         return 0;