Source code for submission s804

Go to diff to previous submission

fr.cpp

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <vector>
  5. #include <map>
  6. #include <set>
  7. #include <string>
  8. #include <cmath>
  9. #include <algorithm>
  10. #include <queue>
  11.  
  12. using namespace std;
  13.  
  14. typedef unsigned long int ulint;
  15.  
  16. struct edge
  17. {
  18.   edge() : dest(), w(0) {}
  19.   edge(int dest, int w) : dest(dest), w(w) {}
  20.   int dest;
  21.   int w; 
  22. };
  23.  
  24. edge graph[1020][1020];
  25. int N;
  26. int M;
  27. int graph_out[1020];
  28.  
  29. int graph_out2[1020];
  30. int parent[1020];
  31. queue<int> Q;
  32. int D[1020];
  33. int R;
  34.  
  35. bool visited[1020];
  36.  
  37. void clear()
  38. {
  39.   M = 0;
  40.   N = 0;
  41.   fill(graph_out, graph_out + 1020, 0);
  42.  
  43.   fill(graph_out2, graph_out2 + 1020, 0);
  44.   fill(D, D + 1020, 0);
  45.   fill(visited, visited + 1020, false);
  46.   while (!Q.empty())
  47.   {
  48.     Q.pop();
  49.   }
  50.  
  51. }
  52.  
  53.  
  54. void solve_parents(int u)
  55. {
  56.     visited[u] = true;
  57.     for (int i = 0; i < graph_out[u]; ++i)
  58.     {
  59.       if (!visited[graph[u][i].dest])
  60.       {
  61. 	parent[graph[u][i].dest] = u;
  62. 	solve_parents(graph[u][i].dest);
  63.       }
  64.     }
  65. }
  66.  
  67. void solve()
  68. {
  69.   parent[R] = 1010;
  70.   solve_parents(R);
  71.  
  72.   // ADD leafs to Q
  73.   for (int i = 1; i <= N; ++i)
  74.   {
  75.     if (graph_out2[i] == 1)
  76.     {
  77.       //printf("leaf %d\n", i);
  78.       Q.push(i);
  79.     }
  80.   }
  81.   while (!Q.empty())
  82.   {
  83.     int u = Q.front();
  84.     Q.pop();
  85.  
  86.     ulint sum = 0;
  87.     for (uint j = 0; j < graph_out[u]; ++j)
  88.     {
  89.       if (graph[u][j].dest == parent[u]) continue;
  90.       if (D[graph[u][j].dest])
  91.       {
  92. 	sum += min(D[graph[u][j].dest], graph[u][j].w);
  93.       }
  94.       else
  95.       {
  96. 	sum += graph[u][j].w;
  97.       }
  98.     }
  99.     D[u] = sum;
  100.     graph_out2[parent[u]]--;
  101.     //printf("parent of %d is %d\n", u, parent[u]);
  102.  
  103.     if (graph_out2[parent[u]] == ((parent[u] == R) ? 0 : 1))
  104.     {
  105.       //printf("new leaf %d (from %d, new leaf def %d)\n", parent[u], u, graph_out2[parent[u]]);
  106.       //cerr << "new leaf\n";
  107.       Q.push(parent[u]);
  108.     }
  109.   }
  110.   printf("%d\n", D[R]);
  111. }
  112.  
  113. int main()
  114. {
  115.   clear();
  116.   while (scanf("%d %d", &N, &R) != EOF)
  117.   {
  118.     for (int i = 0; i < N - 1; ++i)
  119.     {
  120.       int u, v, w;
  121.       scanf("%d %d %d", &u, &v, &w);
  122.       graph[u][graph_out[u]++] = edge(v, w);
  123.       graph[v][graph_out[v]++] = edge(u, w);
  124.       graph_out2[u]++;
  125.       graph_out2[v]++;
  126.  
  127.     }
  128.     solve();
  129.     clear();
  130.   }
  131. }
  132.  

Diff to submission s751

fr.cpp

--- c5.s751.cteam090.fr.cpp.0.fr.cpp
+++ c5.s804.cteam090.fr.cpp.0.fr.cpp
@@ -71,8 +71,9 @@
   
   // ADD leafs to Q
-  for (int i = 0; i < N; ++i)
+  for (int i = 1; i <= N; ++i)
   {
     if (graph_out2[i] == 1)
     {
+      //printf("leaf %d\n", i);
       Q.push(i);
     }
@@ -98,6 +99,9 @@
     D[u] = sum;
     graph_out2[parent[u]]--;
-    if (graph_out2[parent[u]] == 1)
+    //printf("parent of %d is %d\n", u, parent[u]);
+
+    if (graph_out2[parent[u]] == ((parent[u] == R) ? 0 : 1))
     {
+      //printf("new leaf %d (from %d, new leaf def %d)\n", parent[u], u, graph_out2[parent[u]]);
       //cerr << "new leaf\n";
       Q.push(parent[u]);