Go to diff to previous submission
import java.util.HashMap; import java.util.Map; import java.util.Scanner; /** * * @author cteam049 */ public class Main { static class Node { int value; int force; int count; Node parent; public Node(int value) { this.value = value; } } private static boolean appendNode(Node node, int i1, int i2, int i3) { if (nodes.containsKey(i1)) { Node n = nodes.get(i1); Node newNode = new Node(i2); newNode.force = i3; newNode.parent = n; n.sucs.put(i2, newNode); 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 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; } private static void preorder(Node node) { for (Node n : node.sucs.values()) { preorder(n); } } private static int solve(Node node) { if (node.sucs.isEmpty()) { return node.force; } int sum = 0; for (Node n : node.sucs.values()) { sum += solve(n); } if (sum < node.force) { return sum; } return node.force; } private static int solveIterative(Node node) { outer: while (node.parent != null) { if (node.sucs.isEmpty()) { node.count = node.force; } else { for (Node n : node.sucs.values()) { if (n.count == 0) { node = n; continue outer; } } for (Node n : node.sucs.values()) { node.count += n.count; } if (node.count > node.force) node.count = node.force; } node = node.parent; } for (Node n : node.sucs.values()) { node.count += n.count; } return node.count; } int n, c; while (sc.hasNext()) { n = sc.nextInt(); c = sc.nextInt(); Node n1 = new Node(c); n1.parent = null; nodes.put(c, n1); for (int i=0 ; i<n-1 ; i++) { int i1 = sc.nextInt(); int i2 = sc.nextInt(); int i3 = sc.nextInt(); appendNode(null, i1, i2, i3); } parent.sucs.put(0, n1); n1.parent = parent; // preorder(n1); // System.out.println(solve(n1)); } } }
--- 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); }