unknown run-time exception in kattis problem "marbles on a tree"

Viewed 18

I've been trying to implement this solution (https://algorithmist.com/wiki/UVa_10672_-_Marbles_on_a_tree) to this kattis problem (https://open.kattis.com/problems/marblestree). This is a graph theory problem involving a tree and a greedy algorithm similar to DFS. My code works for the sample test case, but generates a run-time exception on the second test case. The problem is, I have no idea where the exception is happening or what the exception is - Kattis gives me no hints. This isn't a memory exceeded or time exceeded deal, as kattis has a seperate notification for those errors; something somewhere is generating an explicit run-time exception and I have no idea where. My guess is that the exception is happening somewhere in the while loop with the condition "que.size() > 0", but I cant find where. Here is the code:

import java.util.*;
import java.io.*;

public class marblestree
{
    public static ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
    public static ArrayList<Integer> values = new ArrayList<>();
    public static ArrayList<Integer> leaves = new ArrayList<>();
    
    public static void main(String args[]) throws IOException
    {
      Scanner in = new Scanner(System.in);
      
      int n = 1;
      while (n > 0)
      {
         n = in.nextInt();
         if (n == 0)
            break;
         for (int i = 0; i < n; i++)
         {
            adjList.add(new ArrayList<Integer>());
         }
         for (int j = 0; j < n; j++)
         {
            in.nextInt();
            values.add(in.nextInt());
            int adjNum = in.nextInt();
            for (int m = 0; m < adjNum; m++)
            {
               adjList.get(in.nextInt() - 1).add(j);
            }
            if (adjNum == 0)
               leaves.add(j);
         }
         
         //System.out.println("adjList: " + adjList);
         
         //handle case
         LinkedList<Integer> que = new LinkedList<>();
         for (Integer y : leaves)
         {
            que.add(y);
         }
         
         int moves = 0;
         
         adjList.get(0).add(0);
         
         while (que.size() > 0)
         {
            //System.out.println("next, this is currently the que: " + que);
            //System.out.println("and these are the values at each vertex:" + values);
            int now = que.poll();
            if (now != 0)
            {
               if (adjList.get(now).get(0) > 0 && !que.contains(adjList.get(now).get(0)))
                  que.add(adjList.get(now).get(0));
               moves += Math.abs(values.get(now) - 1);
               values.set(adjList.get(now).get(0), values.get(adjList.get(now).get(0)) + (values.get(now) - 1));
               values.set(now, 1);
            }
         }
         
         System.out.println(moves);
         
         adjList = new ArrayList<>();
         values = new ArrayList<>();
         leaves = new ArrayList<>();

      }
    }
      
    }
0 Answers
Related