Source code for submission s937

Go to diff to previous submission

Fr.java

  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. class Fr
  5. {
  6.  
  7.     public static void main(String[] args) throws IOException {
  9.  
  10.  
  11.         while(br.ready())
  12.         {
  13.             String line = br.readLine();
  15.             int numNodes = Integer.parseInt(st.nextToken());
  16.             int centralNode = Integer.parseInt(st.nextToken());
  17.             doTestCase(br, numNodes, centralNode);
  18.  
  19.         }
  20.     }
  21.  
  22.     public static void doTestCase(BufferedReader br, int numNodes, int centralNode) throws IOException {
  23.         Node[] nodes = new Node[numNodes];
  24.         for (int i = 1; i <= nodes.length; i++) {
  25.             nodes[i- 1] = new Node(i, i == centralNode);
  26.  
  27.         }
  28.  
  29.  
  30.  
  31.  
  32.         for (int i = 0; i < (numNodes - 1); i++) { // pipes
  33.             String line = br.readLine();
  35.             Node nodeA = nodes[Integer.parseInt(st.nextToken()) - 1];
  36.             Node nodeB = nodes[Integer.parseInt(st.nextToken()) - 1];
  37.             int effort = Integer.parseInt(st.nextToken());
  38.  
  39.             Pipe p = new Pipe(effort, nodeA, nodeB);
  40.             nodeA.addPipe(p);
  41.             nodeB.addPipe(p);
  42.  
  43.         }
  44.  
  45.         System.out.println(nodes[centralNode - 1].getEffort(null));
  46.  
  47.         /*for (int i = 0; i < nodes.length; i++) {
  48.             HubNode hubNode = nodes[i];
  49.          //   System.out.println("node #"+(i+1)+", "+hubNode.getChildren().size()+" children, effort = "+hubNode.getEffort());
  50.  
  51.         }*/
  52.  
  53.  
  54.     }
  55.  
  56.  
  57.  
  58.  
  59. }
  60.  
  61.  
  62. class Node {
  63.  
  64.     protected int id;
  65.     boolean root;
  66.     ArrayList<Pipe> pipes = new ArrayList<Pipe>();
  67.  
  68.  
  69.     public Node(int id, boolean root) {
  70.         this.id = id;
  71.         this.root = root;
  72.     }
  73.  
  74.     public void addPipe(Pipe pipe) {
  75.         //System.out.printf("Add pipe to node %d, %s\n", id, pipe);
  76.         pipes.add(pipe);
  77.     }
  78.  
  79.     public ArrayList<Pipe> getPipes() {
  80.         return pipes;
  81.     }
  82.  
  83.     public Integer getId() {
  84.         return id;
  85.     }
  86.  
  87.     //effort to remove ME
  88.     public int getEffort(Pipe parentPipe) {       
  89.  
  90.         //System.out.printf("GetEffort of node %d\n", id);
  91.  
  92.         int removeMeEffort;
  93.         //nalezt rodicovskou pipu
  94.  
  95.         if(!root) {            
  96.             removeMeEffort = parentPipe.getEffort();
  97.         }else {
  98.  
  99.             removeMeEffort = -1; 
  100.         }
  101.  
  102.         int removeChildrenEffort = 0;
  103.  
  104.  
  105.  
  106.         if(pipes.size() == 1 && !root) { //list
  107.  
  108.             //vzit patricnej node
  109.             /*Pipe p = pipes.get(0);
  110.             Node child = p.getNodeA().getId() == id ? p.getNodeB() : p.getNodeA();
  111.             System.out.printf("LEAF #%d, effort %d", id, removeM);
  112.             return child.getEffort(visitedNodes);
  113.              * */
  114.             //System.out.printf("Leaf %d, effort %d\n", id, removeMeEffort);
  115.             return removeMeEffort;
  116.  
  117.         }else { //hubovej uzel
  118.  
  119.             for(Pipe p : getPipes()) { //prohlidnu kazou pipu
  120.                 Node a = p.getNodeA();
  121.                 Node b = p.getNodeB();
  122.  
  123.                 if(p.equals(parentPipe)) {
  124.                     //pokud jde o rodicovskou trubku
  125.                     continue;
  126.  
  127.                 }else {
  128.                     Node child = a.getId() == id ? b : a;      
  129.                     //System.out.printf("Inner %d asks for effort %d, has effort %d\n", id, child.getId(), removeMeEffort);
  130.                     removeChildrenEffort += child.getEffort(p);                  
  131.                 }         
  132.             }
  133.  
  134.         }
  135.  
  136.         if(root) {
  137.             //System.out.printf("Root, effort %d\n", removeChildrenEffort);
  138.             return removeChildrenEffort;
  139.         }else {
  140.             int effort = removeMeEffort > removeChildrenEffort ? removeChildrenEffort : removeMeEffort;
  141.             //System.out.printf("Inner %d, effort %d\n", id, effort);
  142.             return effort;
  143.         }
  144.     }
  145.  
  146. }
  147.  
  148. /*class RootNode extends HubNode {
  149. }*/
  150.  
  151. class Pipe {
  152.     protected int effort;
  153.     protected Node a, b;
  154.  
  155.     ArrayList<Integer> visitedNodes = new ArrayList<Integer>();
  156.  
  157.     public Pipe(int effort, Node a, Node b) {
  158.         this.effort = effort;
  159.         this.a = a;
  160.         this.b = b;
  161.     }
  162.  
  163.     public int getEffort() {
  164.         return effort;
  165.     }
  166.  
  167.     public Node getNodeA() {
  168.         return a;
  169.     }
  170.  
  171.     public Node getNodeB() {
  172.         return b;
  173.     }
  174.  
  175.     public boolean equals(Pipe p) {
  176.         if(p == null) {
  177.             return false;
  178.         }
  179.         return this.toString().equals(p.toString());
  180.     }
  181.  
  182.     @Override
  183.     public String toString() {
  184.         return "Pipe "+a.getId()+"<->"+b.getId();
  185.     }
  186. }

Diff to submission s892

Fr.java

--- c5.s892.cteam006.fr.java.0.Fr.java
+++ c5.s937.cteam006.fr.java.0.Fr.java
@@ -43,5 +43,5 @@
         }
         
-        System.out.println(nodes[centralNode - 1].getEffort(new ArrayList<Integer>()));
+        System.out.println(nodes[centralNode - 1].getEffort(null));
         
         /*for (int i = 0; i < nodes.length; i++) {
@@ -86,6 +86,5 @@
     
     //effort to remove ME
-    public int getEffort(ArrayList<Integer> visitedNodes) {       
-        visitedNodes.add(id);
+    public int getEffort(Pipe parentPipe) {       
         
         //System.out.printf("GetEffort of node %d\n", id);
@@ -94,28 +93,25 @@
         //nalezt rodicovskou pipu
         
-        if(!root) {
-            Pipe parentPipe = null;
-        
-            for(Pipe p : getPipes()) {
-                //System.out.println(p);
-                if(visitedNodes.contains(p.getNodeA().getId()) || 
-                        visitedNodes.contains(p.getNodeB().getId())) {
-                    parentPipe = p;
-                    break;
-                }
-            }
-            
+        if(!root) {            
             removeMeEffort = parentPipe.getEffort();
         }else {
             
-            removeMeEffort = -1;
-            
+            removeMeEffort = -1; 
         }
+        
         int removeChildrenEffort = 0;
         
         
         
-        if(pipes.size() == 1) { //list
-            return pipes.get(0).getEffort();
+        if(pipes.size() == 1 && !root) { //list
+            
+            //vzit patricnej node
+            /*Pipe p = pipes.get(0);
+            Node child = p.getNodeA().getId() == id ? p.getNodeB() : p.getNodeA();
+            System.out.printf("LEAF #%d, effort %d", id, removeM);
+            return child.getEffort(visitedNodes);
+             * */
+            //System.out.printf("Leaf %d, effort %d\n", id, removeMeEffort);
+            return removeMeEffort;
             
         }else { //hubovej uzel
@@ -125,12 +121,12 @@
                 Node b = p.getNodeB();
                 
-                if(visitedNodes.contains(a.getId()) &&
-                        visitedNodes.contains(b.getId())) {
-                    //pokud mne spojuje s nodem kde jsem uz byl, ignoruju
+                if(p.equals(parentPipe)) {
+                    //pokud jde o rodicovskou trubku
                     continue;
                     
                 }else {
-                    Node child = a.getId() == id ? b : a;       
-                    removeChildrenEffort += child.getEffort(visitedNodes);                  
+                    Node child = a.getId() == id ? b : a;      
+                    //System.out.printf("Inner %d asks for effort %d, has effort %d\n", id, child.getId(), removeMeEffort);
+                    removeChildrenEffort += child.getEffort(p);                  
                 }         
             }
@@ -139,7 +135,10 @@
         
         if(root) {
+            //System.out.printf("Root, effort %d\n", removeChildrenEffort);
             return removeChildrenEffort;
         }else {
-            return removeMeEffort > removeChildrenEffort ? removeChildrenEffort : removeMeEffort;
+            int effort = removeMeEffort > removeChildrenEffort ? removeChildrenEffort : removeMeEffort;
+            //System.out.printf("Inner %d, effort %d\n", id, effort);
+            return effort;
         }
     }
@@ -174,4 +173,11 @@
     }
     
+    public boolean equals(Pipe p) {
+        if(p == null) {
+            return false;
+        }
+        return this.toString().equals(p.toString());
+    }
+    
     @Override
     public String toString() {