Source code for submission s751

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 = 0; i < N; ++i)
  74.   {
  75.     if (graph_out2[i] == 1)
  76.     {
  77.       Q.push(i);
  78.     }
  79.   }
  80.   while (!Q.empty())
  81.   {
  82.     int u = Q.front();
  83.     Q.pop();
  84.  
  85.     ulint sum = 0;
  86.     for (uint j = 0; j < graph_out[u]; ++j)
  87.     {
  88.       if (graph[u][j].dest == parent[u]) continue;
  89.       if (D[graph[u][j].dest])
  90.       {
  91. 	sum += min(D[graph[u][j].dest], graph[u][j].w);
  92.       }
  93.       else
  94.       {
  95. 	sum += graph[u][j].w;
  96.       }
  97.     }
  98.     D[u] = sum;
  99.     graph_out2[parent[u]]--;
  100.     if (graph_out2[parent[u]] == 1)
  101.     {
  102.       //cerr << "new leaf\n";
  103.       Q.push(parent[u]);
  104.     }
  105.   }
  106.   printf("%d\n", D[R]);
  107. }
  108.  
  109. int main()
  110. {
  111.   clear();
  112.   while (scanf("%d %d", &N, &R) != EOF)
  113.   {
  114.     for (int i = 0; i < N - 1; ++i)
  115.     {
  116.       int u, v, w;
  117.       scanf("%d %d %d", &u, &v, &w);
  118.       graph[u][graph_out[u]++] = edge(v, w);
  119.       graph[v][graph_out[v]++] = edge(u, w);
  120.       graph_out2[u]++;
  121.       graph_out2[v]++;
  122.  
  123.     }
  124.     solve();
  125.     clear();
  126.   }
  127. }
  128.  

Diff to submission s723

fr.cpp

--- c5.s723.cteam090.fr.cpp.0.fr.cpp
+++ c5.s751.cteam090.fr.cpp.0.fr.cpp
@@ -55,5 +55,5 @@
 {
     visited[u] = true;
-    for (int i = 0; i < N; ++i)
+    for (int i = 0; i < graph_out[u]; ++i)
     {
       if (!visited[graph[u][i].dest])