Source code for submission s710

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. QL=0;
  127. for (int i = 0; i < V + 1; i++) {
  128. if (ADJ_N[i] == 1 && i != KOR) {
  129. QUEUE[QL++] = i;
  130. debug("LIST: %d\n", i);
  131. }
  132. }
  133.  
  134. while (QZ<QL) {
  135. DESTROY_ALL_BELOW(QUEUE[QZ]);
  136. for (int i = 0; i < ADJ_N[QUEUE[QZ]]; i++) {
  137. if (COST[ADJACENT[QUEUE[QZ]][i]] == -1) {
  138. int p=ADJACENT[QUEUE[QZ]][i];
  139. int pocet=0;
  140. for (int j =0;j<ADJ_N[p];j++) {
  141. if(COST[ADJACENT[p][j]]==-1)
  142. pocet++;
  143. }
  144. if (pocet==1 && p !=KOR)
  145. QUEUE[QL++] = ADJACENT[QUEUE[QZ]][i];
  146. if (pocet==0)
  147. QUEUE[QL++] = ADJACENT[QUEUE[QZ]][i];
  148. }
  149. }
  150. QZ++;
  151. }
  152.  
  153. printf("%ld\n", COST[KOR]);
  154.  
  155. // printf("%ld\n", RECURSE(-1, -1, KOR));
  156. }
  157.  
  158. int main() {
  159. while (true) {
  160. if (scanf("%d%d", &V, &KOR) != 2) break;
  161. GO();
  162. }
  163. return 0;
  164. }
  165.  

Diff to submission s620

fr.cpp

--- c5.s620.cteam032.fr.cpp.0.fr.cpp
+++ c5.s710.cteam032.fr.cpp.0.fr.cpp
@@ -124,4 +124,5 @@
 
         QZ=0;
+        QL=0;
         for (int i = 0; i < V + 1; i++) {
                 if (ADJ_N[i] == 1 && i != KOR) {
@@ -135,5 +136,14 @@
                 for (int i = 0; i < ADJ_N[QUEUE[QZ]]; i++) {
                         if (COST[ADJACENT[QUEUE[QZ]][i]] == -1) {
-                                QUEUE[QL++] = ADJACENT[QUEUE[QZ]][i];
+                                int p=ADJACENT[QUEUE[QZ]][i];
+                                int pocet=0;
+                                for (int j =0;j<ADJ_N[p];j++) {
+                                        if(COST[ADJACENT[p][j]]==-1)
+                                                pocet++;
+                                }
+                                if (pocet==1 && p !=KOR)
+                                        QUEUE[QL++] = ADJACENT[QUEUE[QZ]][i];
+                                if (pocet==0)
+                                        QUEUE[QL++] = ADJACENT[QUEUE[QZ]][i];
                         }
                 }