Untitled
unknown
java
2 years ago
5.1 kB
5
Indexable
import java.util.*; public class Main { public static void main(String[] args){ Scanner scanner = new Scanner(System.in); int t = scanner.nextInt(); Integer[][] timeData = new Integer[t][4]; Integer[] nodeNumbers = new Integer[t+1]; int time = 0; for (int i = 0; i < t; i++){ timeData[i][0] = scanner.nextInt(); timeData[i][1] = scanner.nextInt(); timeData[i][2] = scanner.nextInt(); timeData[i][3] = scanner.nextInt(); time += timeData[i][0]; } for (int i = 0; i < t + 1; i++){ nodeNumbers[i] = i; } int e = scanner.nextInt(); Map<Integer, Node> setUpMap = new HashMap<>(); for(Integer i = 0; i < e; i++){ Integer prev = scanner.nextInt(); nodeNumbers[prev] = 0; Integer next = scanner.nextInt(); nodeNumbers[next] = 0; if (!setUpMap.containsKey(prev)) { Node node = new Node(); node.setId(prev); node.addNext(next); setUpMap.put(prev, node); } else { Node node = setUpMap.get(prev); ArrayList<Integer> nextNodes = node.getNext(); if (!nextNodes.contains(next)){ node.addNext(next); } } if (!setUpMap.containsKey(next)){ Node node = new Node(); node.setId(next); node.addPrev(prev); setUpMap.put(next, node); } else { Node node = setUpMap.get(next); ArrayList<Integer> prevNodes = node.getPrev(); if (!prevNodes.contains(prev)){ node.addPrev(prev); } } } for(int i = 0; i < t + 1; i++){ if (nodeNumbers[i] != 0){ Node node = new Node(); node.setId(i); setUpMap.put(i, node); } } int fullScore = Integer.MIN_VALUE; int maxScore = Integer.MAX_VALUE; int score = 0; int idToDel = 0; for (int i = 0; i < t; i++){ ArrayList<Node> nodesToCheck = returnNoNext(setUpMap); maxScore = Integer.MAX_VALUE; for (int j = 0; j < nodesToCheck.size(); j++){ int nodeId = nodesToCheck.get(j).id; score = timeData[nodeId-1][1]*time*time + timeData[nodeId-1][2]*time + timeData[nodeId-1][3]; if (score < maxScore){ maxScore = score; idToDel = nodeId; } } if (maxScore > fullScore){ fullScore = maxScore; } time -= timeData[idToDel-1][0]; setUpMap.remove(idToDel); setUpMap = removeNextNodes(setUpMap, idToDel); } System.out.println(fullScore); } public static ArrayList<Node> returnNoNext (Map<Integer, Node> map){ ArrayList<Node> nodes = new ArrayList<>(); for (Integer key : map.keySet()){ Node node = map.get(key); if (node.next.size() == 0){ nodes.add(node); } } return nodes; } public static Map<Integer, Node> removeNextNodes (Map<Integer, Node> map, int nodeId){ Map<Integer, Node> result = new HashMap<>(); for (Integer key : map.keySet()){ Node node = map.get(key); int pos = node.next.indexOf(nodeId); if (pos != -1){ node.next.remove(pos); } result.put(key, node); } return result; } } class Node implements Comparable<Node>{ int id; ArrayList<Integer> prev = new ArrayList<>(); ArrayList<Integer> next = new ArrayList<>(); public Node(int id, ArrayList<Integer> prev, ArrayList<Integer> next) { this.id = id; this.prev = prev; this.next = next; } @Override public String toString() { return "Node{" + "id=" + id + ", prev=" + prev + ", next=" + next + '}'; } @Override public int compareTo(Node other) { // sort based on the smallest t value return Integer.compare(this.next.size(), other.next.size()); } public void addPrev(Integer prevInt){ prev.add(prevInt); } public void addNext(Integer nextInt){ next.add(nextInt); } public Node() { } public int getId() { return id; } public void setId(int id) { this.id = id; } public ArrayList<Integer> getPrev() { return prev; } public void setPrev(ArrayList<Integer> prev) { this.prev = prev; } public ArrayList<Integer> getNext() { return next; } public void setNext(ArrayList<Integer> next) { this.next = next; } }
Editor is loading...