Source code for submission s906

Go to diff to previous submission

fr.cpp

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <set>
  6. #include <queue>
  7. #include <map>
  8. #include <string>
  9. #include <cmath>
  10. #include <cstdlib>
  11. #include <cstring>
  12. #include <sstream>
  13.  
  14. #include <stdio.h>
  15. #include <ctype.h>
  16. #include <math.h>
  17. #include <string.h>
  18. #include <stdlib.h>
  19.  
  20. using namespace std;
  21.  
  22. #define X first
  23. #define Y second
  24. #define MP make_pair
  25. #define PB push_back
  26. #define SZ size
  27.  
  28. int main () {
  29. int hodnota[1005];
  30. int pom[1005], pom2[1005];
  31. int hrany[1005][1005];
  32. int sus[1005][1005];
  33. queue<int> t;
  34.  
  35. int i, ii, n, koren, a, b, c;
  36. while (scanf("%d %d", &n, &koren) > 0) {
  37. for (i = 1; i < 1002; i++) {
  38. pom[i] = 0;
  39. hodnota[i] = 0;
  40. pom2[i] = 0;
  41. }
  42. for (i = 1; i < 1002; i++) {
  43. for (ii = 1; ii < 1002; ii++) {
  44. hrany[i][ii] = 0;
  45. }
  46. }
  47. for (i = 0; i < n - 1; i++) {
  48. scanf("%d %d %d", &a, &b, &c);
  49. pom[a] = pom[a] + 1;
  50. pom[b] = pom[b] + 1;
  51. //cout << pom[1] << endl;
  52. hrany[a][b] = c;
  53. hrany[b][a] = c;
  54. sus[a][pom[a] - 1] = b;
  55. sus[b][pom[b] - 1] = a;
  56. pom2[a] = pom2[a] + 1;
  57. pom2[b] = pom2[b] + 1;
  58. }
  59. for (i = 1; i <= n; i++) {
  60. if (pom[i] == 1)
  61. t.push(i);
  62. }
  63. while(!t.empty()) {
  64. n = t.front();
  65. t.pop();
  66.  
  67. //cout << n << "aaa" << pom[1] << endl;
  68. for (ii = 0; ii < pom[n]; ii++) {
  69.  
  70. //cout << sus[n][ii] << "bbb" << endl;
  71. if (hodnota[n] == 0 || hodnota[n] > hrany[n][sus[n][ii]])
  72. hodnota[sus[n][ii]] = hodnota[sus[n][ii]] + hrany[n][sus[n][ii]];
  73. else
  74. hodnota[sus[n][ii]] = hodnota[sus[n][ii]] + hodnota[n];
  75. pom2[sus[n][ii]]--;
  76. if (pom2[sus[n][ii]] == 1)
  77. t.push(sus[n][ii]);
  78. //cout << sus[n][ii] << " " << hodnota[sus[n][ii]] << " " << n << endl;
  79. }
  80. pom2[n] = -1;
  81. }
  82. cout << hodnota[koren] << endl;
  83. }
  84. return 0;
  85. }
  86.  

Diff to submission s899

fr.cpp

--- c5.s899.cteam077.fr.cpp.0.fr.cpp
+++ c5.s906.cteam077.fr.cpp.0.fr.cpp
@@ -27,5 +27,4 @@
 
 int main () {
-        vector<pair <int, int> > sused;
         int hodnota[1005];
         int pom[1005], pom2[1005];
@@ -39,4 +38,5 @@
                         pom[i] = 0;
                         hodnota[i] = 0;
+                        pom2[i] = 0;
                 }
                 for (i = 1; i < 1002; i++) {
@@ -58,8 +58,4 @@
                 }
                 for (i = 1; i <= n; i++) {
-                        sused.PB(MP(pom[i], i));
-                }
-                sort(sused.begin(), sused.end());
-                for (i = 1; i <= n; i++) {
                         if (pom[i] == 1)
                                 t.push(i);
@@ -85,5 +81,4 @@
                 }
                 cout << hodnota[koren] << endl;
-                sused.clear();
         }
         return 0;