Untitled

 avatar
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...