Source code for submission s1129

Go to diff to previous submission

Main.java

  1.  
  2. import java.util.HashMap;
  3. import java.util.Map;
  4. import java.util.Scanner;
  5.  
  6. /**
  7.  *
  8.  * @author cteam049
  9.  */
  10. public class Main {
  11.  
  12. static Map<Integer, Node> nodes = new HashMap<Integer, Main.Node>();
  13.  
  14. static class Node {
  15. Map<Integer, Node> sucs = new HashMap<Integer, Main.Node>();
  16. int value;
  17. int force;
  18. int count;
  19. Node parent;
  20.  
  21. public Node(int value) {
  22. this.value = value;
  23. }
  24. }
  25.  
  26. private static boolean appendNode(Node node, int i1, int i2, int i3) {
  27. if (nodes.containsKey(i1)) {
  28. Node n = nodes.get(i1);
  29.  
  30. Node newNode = new Node(i2);
  31. newNode.force = i3;
  32. newNode.parent = n;
  33. n.sucs.put(i2, newNode);
  34.  
  35. nodes.put(i2, newNode);
  36. } else if (nodes.containsKey(i2)) {
  37. Node n = nodes.get(i2);
  38.  
  39. Node newNode = new Node(i1);
  40. newNode.force = i3;
  41. newNode.parent = n;
  42. n.sucs.put(i1, newNode);
  43.  
  44. nodes.put(i1, newNode);
  45. }
  46. return true;
  47. // if (node.value == i1) {
  48. // Node n = new Node(i2);
  49. // n.force = i3;
  50. // n.parent = node;
  51. // node.sucs.put(i2, n);
  52. //
  53. // return true;
  54. // } else if (node.value == i2) {
  55. // Node n = new Node(i1);
  56. // n.force = i3;
  57. // n.parent = node;
  58. // node.sucs.put(i1, n);
  59. //
  60. // return true;
  61. // } else if (node.sucs.containsKey(i1)) {
  62. // return appendNode(node.sucs.get(i1), i1, i2, i3);
  63. // } else if (node.sucs.containsKey(i2)) {
  64. // return appendNode(node.sucs.get(i2), i1, i2, i3);
  65. // } else {
  66. // for (Node tmp : node.sucs.values()) {
  67. // if (appendNode(tmp, i1, i2, i3)) return true;
  68. // }
  69. // }
  70. // return false;
  71. }
  72.  
  73.  
  74. private static void preorder(Node node) {
  75. System.out.println(node.value);
  76. for (Node n : node.sucs.values()) {
  77. preorder(n);
  78. }
  79.  
  80. }
  81.  
  82. private static int solve(Node node) {
  83. if (node.sucs.isEmpty()) {
  84. return node.force;
  85. }
  86. int sum = 0;
  87. for (Node n : node.sucs.values()) {
  88. sum += solve(n);
  89. }
  90. if (sum < node.force) {
  91. return sum;
  92. }
  93. return node.force;
  94. }
  95.  
  96. private static int solveIterative(Node node) {
  97. outer:
  98. while (node.parent != null) {
  99. if (node.sucs.isEmpty()) {
  100. node.count = node.force;
  101. } else {
  102. for (Node n : node.sucs.values()) {
  103. if (n.count == 0) {
  104. node = n;
  105. continue outer;
  106. }
  107. }
  108. for (Node n : node.sucs.values()) {
  109. node.count += n.count;
  110. }
  111. if (node.count > node.force) node.count = node.force;
  112. }
  113. node = node.parent;
  114. }
  115. for (Node n : node.sucs.values()) {
  116. node.count += n.count;
  117. }
  118. return node.count;
  119. }
  120.  
  121. public static void main(String[] args) {
  122. Scanner sc = new Scanner(System.in);
  123. String line = null;
  124. int n, c;
  125. while (sc.hasNext()) {
  126. n = sc.nextInt();
  127. c = sc.nextInt();
  128. Node n1 = new Node(c);
  129. n1.force = Integer.MAX_VALUE;
  130. n1.parent = null;
  131. nodes.put(c, n1);
  132.  
  133. for (int i=0 ; i<n-1 ; i++) {
  134. int i1 = sc.nextInt();
  135. int i2 = sc.nextInt();
  136. int i3 = sc.nextInt();
  137. appendNode(null, i1, i2, i3);
  138. }
  139.  
  140. Node parent = new Node(Integer.MAX_VALUE);
  141. parent.sucs.put(0, n1);
  142. parent.force = Integer.MAX_VALUE;
  143. n1.parent = parent;
  144. System.out.println(solveIterative(n1));
  145. // preorder(n1);
  146. // System.out.println(solve(n1));
  147. }
  148. }
  149.  
  150. }
  151.  

Diff to submission s1055

Main.java

--- c5.s1055.cteam049.fr.java.0.Main.java
+++ c5.s1129.cteam049.fr.java.0.Main.java
@@ -10,4 +10,6 @@
 public class Main {
 
+    static Map<Integer, Node> nodes = new HashMap<Integer, Main.Node>();
+    
     static class Node {
         Map<Integer, Node> sucs = new HashMap<Integer, Main.Node>();
@@ -23,28 +25,48 @@
     
     private static boolean appendNode(Node node, int i1, int i2, int i3) {
-        if (node.value == i1) {
-            Node n = new Node(i2);
-            n.force = i3;
-            n.parent = node;
-            node.sucs.put(i2, n);
+        if (nodes.containsKey(i1)) {
+            Node n = nodes.get(i1);
             
-            return true;
-        } else if (node.value == i2) {
-            Node n = new Node(i1);
-            n.force = i3;
-            n.parent = node;
-            node.sucs.put(i1, n);
+            Node newNode = new Node(i2);
+            newNode.force = i3;
+            newNode.parent = n;
+            n.sucs.put(i2, newNode);
             
-            return true;
-        } else if (node.sucs.containsKey(i1)) {
-            return appendNode(node.sucs.get(i1), i1, i2, i3);
-        } else if (node.sucs.containsKey(i2)) {
-            return appendNode(node.sucs.get(i2), i1, i2, i3);
-        } else {
-            for (Node tmp : node.sucs.values()) {
-                if (appendNode(tmp, i1, i2, i3)) return true;
-            }
+            nodes.put(i2, newNode);
+        } else if (nodes.containsKey(i2)) {
+            Node n = nodes.get(i2);
+            
+            Node newNode = new Node(i1);
+            newNode.force = i3;
+            newNode.parent = n;
+            n.sucs.put(i1, newNode);
+            
+            nodes.put(i1, newNode);
         }
-        return false;
+        return true;
+//        if (node.value == i1) {
+//            Node n = new Node(i2);
+//            n.force = i3;
+//            n.parent = node;
+//            node.sucs.put(i2, n);
+//            
+//            return true;
+//        } else if (node.value == i2) {
+//            Node n = new Node(i1);
+//            n.force = i3;
+//            n.parent = node;
+//            node.sucs.put(i1, n);
+//            
+//            return true;
+//        } else if (node.sucs.containsKey(i1)) {
+//            return appendNode(node.sucs.get(i1), i1, i2, i3);
+//        } else if (node.sucs.containsKey(i2)) {
+//            return appendNode(node.sucs.get(i2), i1, i2, i3);
+//        } else {
+//            for (Node tmp : node.sucs.values()) {
+//                if (appendNode(tmp, i1, i2, i3)) return true;
+//            }
+//        }
+//        return false;
     }
     
@@ -75,10 +97,8 @@
         outer:
         while (node.parent != null) {
-//            System.out.println("Uzel " + node.value);
             if (node.sucs.isEmpty()) {
                 node.count = node.force;
             } else {
                 for (Node n : node.sucs.values()) {
-//                    System.out.println("Potomek " + n.value);
                     if (n.count == 0) {
                         node = n;
@@ -93,6 +113,8 @@
             node = node.parent;
         }
-//        System.out.println("Uzel " + node.value);
-        return node.sucs.get(0).count;
+        for (Node n : node.sucs.values()) {
+            node.count += n.count;
+        }
+        return node.count;
     }
     
@@ -107,4 +129,5 @@
             n1.force = Integer.MAX_VALUE;
             n1.parent = null;
+            nodes.put(c, n1);
             
             for (int i=0 ; i<n-1 ; i++) {
@@ -112,5 +135,5 @@
                 int i2 = sc.nextInt();
                 int i3 = sc.nextInt();
-                appendNode(n1, i1, i2, i3);
+                appendNode(null, i1, i2, i3);
             }