Source code for submission s892

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(new ArrayList<Integer>()));
  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(ArrayList<Integer> visitedNodes) {       
  89.         visitedNodes.add(id);
  90.  
  91.         //System.out.printf("GetEffort of node %d\n", id);
  92.  
  93.         int removeMeEffort;
  94.         //nalezt rodicovskou pipu
  95.  
  96.         if(!root) {
  97.             Pipe parentPipe = null;
  98.  
  99.             for(Pipe p : getPipes()) {
  100.                 //System.out.println(p);
  101.                 if(visitedNodes.contains(p.getNodeA().getId()) || 
  102.                         visitedNodes.contains(p.getNodeB().getId())) {
  103.                     parentPipe = p;
  104.                     break;
  105.                 }
  106.             }
  107.  
  108.             removeMeEffort = parentPipe.getEffort();
  109.         }else {
  110.  
  111.             removeMeEffort = -1;
  112.  
  113.         }
  114.         int removeChildrenEffort = 0;
  115.  
  116.  
  117.  
  118.         if(pipes.size() == 1) { //list
  119.             return pipes.get(0).getEffort();
  120.  
  121.         }else { //hubovej uzel
  122.  
  123.             for(Pipe p : getPipes()) { //prohlidnu kazou pipu
  124.                 Node a = p.getNodeA();
  125.                 Node b = p.getNodeB();
  126.  
  127.                 if(visitedNodes.contains(a.getId()) &&
  128.                         visitedNodes.contains(b.getId())) {
  129.                     //pokud mne spojuje s nodem kde jsem uz byl, ignoruju
  130.                     continue;
  131.  
  132.                 }else {
  133.                     Node child = a.getId() == id ? b : a;       
  134.                     removeChildrenEffort += child.getEffort(visitedNodes);                  
  135.                 }         
  136.             }
  137.  
  138.         }
  139.  
  140.         if(root) {
  141.             return removeChildrenEffort;
  142.         }else {
  143.             return removeMeEffort > removeChildrenEffort ? removeChildrenEffort : removeMeEffort;
  144.         }
  145.     }
  146.  
  147. }
  148.  
  149. /*class RootNode extends HubNode {
  150. }*/
  151.  
  152. class Pipe {
  153.     protected int effort;
  154.     protected Node a, b;
  155.  
  156.     ArrayList<Integer> visitedNodes = new ArrayList<Integer>();
  157.  
  158.     public Pipe(int effort, Node a, Node b) {
  159.         this.effort = effort;
  160.         this.a = a;
  161.         this.b = b;
  162.     }
  163.  
  164.     public int getEffort() {
  165.         return effort;
  166.     }
  167.  
  168.     public Node getNodeA() {
  169.         return a;
  170.     }
  171.  
  172.     public Node getNodeB() {
  173.         return b;
  174.     }
  175.  
  176.     @Override
  177.     public String toString() {
  178.         return "Pipe "+a.getId()+"<->"+b.getId();
  179.     }
  180. }

Diff to submission s717

Fr.java

--- c5.s717.cteam006.fr.java.0.Fr.java
+++ c5.s892.cteam006.fr.java.0.Fr.java
@@ -21,50 +21,33 @@
     
     public static void doTestCase(BufferedReader br, int numNodes, int centralNode) throws IOException {
-        HubNode[] nodes = new HubNode[numNodes];
-        for (int i = 0; i < nodes.length; i++) {
-            nodes[i] = new HubNode();
+        Node[] nodes = new Node[numNodes];
+        for (int i = 1; i <= nodes.length; i++) {
+            nodes[i- 1] = new Node(i, i == centralNode);
 
         }
         
-        nodes[centralNode - 1].setCentral();
 
         
         
-        for (int i = 0; i < (numNodes - 1); i++) {
+        for (int i = 0; i < (numNodes - 1); i++) { // pipes
             String line = br.readLine();
             StringTokenizer st = new StringTokenizer(line);
-            int nodeA = Integer.parseInt(st.nextToken());
-            int nodeB = Integer.parseInt(st.nextToken());
+            Node nodeA = nodes[Integer.parseInt(st.nextToken()) - 1];
+            Node nodeB = nodes[Integer.parseInt(st.nextToken()) - 1];
             int effort = Integer.parseInt(st.nextToken());
             
-            if(nodeA == centralNode || nodeB == centralNode) { //jeden z nich je central
-                if(nodeA == centralNode) {
-                    nodes[nodeA - 1].addChild(nodes[nodeB - 1]);
-                    nodes[nodeB - 1].setEffort(effort);
-                    
-                }else {
-                    nodes[nodeB - 1].addChild(nodes[nodeA - 1]);
-                    nodes[nodeA - 1].setEffort(effort);
-                }
-            }else { //ani jeden
-                if(!nodes[nodeA - 1].hasSetEffort()) { //na tenhle jsem jeste nenastavil effort
-                    nodes[nodeA - 1].setEffort(effort);
-                    nodes[nodeB - 1].addChild(nodes[nodeA - 1]);
-                }else {
-                    nodes[nodeB - 1].setEffort(effort);
-                    nodes[nodeA - 1].addChild(nodes[nodeB - 1]);
-                }
-                                
-            }
+            Pipe p = new Pipe(effort, nodeA, nodeB);
+            nodeA.addPipe(p);
+            nodeB.addPipe(p);
 
         }
         
-        System.out.println(nodes[centralNode - 1].getEffort());
+        System.out.println(nodes[centralNode - 1].getEffort(new ArrayList<Integer>()));
         
-        for (int i = 0; i < nodes.length; i++) {
+        /*for (int i = 0; i < nodes.length; i++) {
             HubNode hubNode = nodes[i];
          //   System.out.println("node #"+(i+1)+", "+hubNode.getChildren().size()+" children, effort = "+hubNode.getEffort());
 
-        }
+        }*/
 
 
@@ -77,48 +60,121 @@
 
 
-class HubNode {
+class Node {
     
-    protected int effort = 0;
-    protected boolean setEffort = false;
-    protected boolean central = false;
-    protected ArrayList<HubNode> children = new ArrayList<HubNode>();
+    protected int id;
+    boolean root;
+    ArrayList<Pipe> pipes = new ArrayList<Pipe>();
     
-    public int getEffort() {
+    
+    public Node(int id, boolean root) {
+        this.id = id;
+        this.root = root;
+    }
+    
+    public void addPipe(Pipe pipe) {
+        //System.out.printf("Add pipe to node %d, %s\n", id, pipe);
+        pipes.add(pipe);
+    }
+    
+    public ArrayList<Pipe> getPipes() {
+        return pipes;
+    }
+    
+    public Integer getId() {
+        return id;
+    }
+    
+    //effort to remove ME
+    public int getEffort(ArrayList<Integer> visitedNodes) {       
+        visitedNodes.add(id);
         
-        if(children.size() == 0) {// System.out.println("getChildren == 0");
-            //koncovej uzel
-            return effort;
-        }
+        //System.out.printf("GetEffort of node %d\n", id);
         
-        int childEffort = 0;
-        for(HubNode n : getChildren()) {
-            childEffort += n.getEffort();
+        int removeMeEffort;
+        //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;
+                }
+            }
+            
+            removeMeEffort = parentPipe.getEffort();
+        }else {
+            
+            removeMeEffort = -1;
+            
         }
+        int removeChildrenEffort = 0;
+        
         
-        return (effort > childEffort || central) ? childEffort : effort;
         
+        if(pipes.size() == 1) { //list
+            return pipes.get(0).getEffort();
+            
+        }else { //hubovej uzel
+            
+            for(Pipe p : getPipes()) { //prohlidnu kazou pipu
+                Node a = p.getNodeA();
+                Node b = p.getNodeB();
+                
+                if(visitedNodes.contains(a.getId()) &&
+                        visitedNodes.contains(b.getId())) {
+                    //pokud mne spojuje s nodem kde jsem uz byl, ignoruju
+                    continue;
+                    
+                }else {
+                    Node child = a.getId() == id ? b : a;       
+                    removeChildrenEffort += child.getEffort(visitedNodes);                  
+                }         
+            }
+            
+        }
         
+        if(root) {
+            return removeChildrenEffort;
+        }else {
+            return removeMeEffort > removeChildrenEffort ? removeChildrenEffort : removeMeEffort;
+        }
     }
     
-    void setCentral() {
-        central = true;
+}
+
+/*class RootNode extends HubNode {
+}*/
+
+class Pipe {
+    protected int effort;
+    protected Node a, b;
+    
+    ArrayList<Integer> visitedNodes = new ArrayList<Integer>();
+    
+    public Pipe(int effort, Node a, Node b) {
+        this.effort = effort;
+        this.a = a;
+        this.b = b;
     }
     
-    public boolean hasSetEffort() {
-        return setEffort;
+    public int getEffort() {
+        return effort;
     }
     
-    public void setEffort(int effort) {
-        setEffort = true;
-        this.effort = effort;
+    public Node getNodeA() {
+        return a;
     }
     
-    public ArrayList<HubNode> getChildren() {
-        return children;
+    public Node getNodeB() {
+        return b;
     }
     
-    public void addChild(HubNode child) {
-       // System.out.println("Adding child ");
-        children.add(child);
+    @Override
+    public String toString() {
+        return "Pipe "+a.getId()+"<->"+b.getId();
     }
 }
\ No newline at end of file