You are viewing a single comment's thread. Return to all comments →
Tried this. But it is very slow because of its terrible complexity and it times out for all large inputs:
static int[] solve(int[][] tree, int[][] queries) { int low = 0, high = 0; ArrayList<Integer> maxPathCostArray = new ArrayList<Integer>(); maxPathCostArray = getMaxPathCostArray(tree); int[] result = new int[queries.length]; for(int i = 0; i < queries.length; i++){ low = queries[i][0]; high = queries[i][1]; for(int k = 0; k < maxPathCostArray.size(); k++){ if(maxPathCostArray.get(k) >= low && maxPathCostArray.get(k) <= high) result[i]++; } } return result; } static ArrayList<Integer> getMaxPathCostArray(int[][] tree){ int n = tree.length + 1; //number of nodes int maxPathCost = 0; int from = 0; int to = 0; ArrayList<Integer> maxPathCostArray = new ArrayList<Integer>(); //Loop through all nodes for(int i = 1; i <= n - 1; i++){ from = i; for(int j = i + 1; j <= n; j++) { to = j; maxPathCostArray.add(getMaxCostForPath(from, to, tree)); } } return maxPathCostArray; } static int getMaxCostForPath(int from, int to, int[][] tree){ ArrayList<Integer> visited = new ArrayList<Integer>(); Stack<Integer> stack = new Stack<Integer>(); stack.push(from); visited.add(from); int maxCost = 0; boolean pathFound = false; int newNode = 0; int x = 0, y = 0; while(stack.peek() != to){ for(int i = 0; i < tree.length; i++){ if(stack.peek() == tree[i][0] && !visited.contains(tree[i][1])){ newNode = tree[i][1]; pathFound = true; } if(stack.peek() == tree[i][1] && !visited.contains(tree[i][0])){ newNode = tree[i][0]; pathFound = true; } } if(stack.peek() != to && pathFound == false) stack.pop(); else { stack.push(newNode); visited.add(newNode); pathFound = false; } } while(stack.peek() != from){ x = stack.pop(); y = stack.peek(); for(int i = 0; i < tree.length; i++){ if((tree[i][0] == x && tree[i][1] == y) || (tree[i][0] == y && tree[i][1] == x)) if(tree[i][2] > maxCost) maxCost = tree[i][2]; } } return maxCost; }
Seems like cookies are disabled on this browser, please enable them to open this website
Super Maximum Cost Queries
You are viewing a single comment's thread. Return to all comments →
Tried this. But it is very slow because of its terrible complexity and it times out for all large inputs: