## Problem Info

USACO 2019 Feb Plat - Moorio Kart

## Question

My Java code is passing the first 12 test cases, but is getting a wrong answer for the last 5.

## What I’ve Tried

I downloaded the test cases and noticed the last 5 have N = 1500, while the other 12 have N < 1000. What confuses me is that I’m not sure how that’d affect getting the wrong answer. It seems like that should cause a TLE, but it’s not (and far from it when I run it locally).

I thought it was maybe an integer overflow error, but I’ve checked my code multiple times and can’t find any. Also, when I change the other downloaded test cases (Changing X, Y, or adding more meadows), I get the same answer compared to the official solution.

I’ve also generated small test cases and stress tested them with the official solution code and can’t find anything wrong.

## My Work

```
import java.io.*;
import java.util.*;
public class Mooriokart {
public static HashMap<Integer, ArrayList<Pair>> farm; public static ArrayList<ArrayList<Integer>> comp;
public static boolean[][] visited;
public static int num; public static int m; public static int X; public static int Y; public static int mod = (int) 1E9+7;
public static void main(String[] args) throws IOException {
BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer l1 = new StringTokenizer(scan.readLine());
num = Integer.parseInt(l1.nextToken()); m = Integer.parseInt(l1.nextToken()); X = Integer.parseInt(l1.nextToken()); int Y = Integer.parseInt(l1.nextToken());
farm = new HashMap<>();
for (int i = 0;i<num;i++) farm.put(i,new ArrayList<>());
for (int i = 0;i<m;i++) {
StringTokenizer st = new StringTokenizer(scan.readLine());
int a = Integer.parseInt(st.nextToken())-1; int b = Integer.parseInt(st.nextToken())-1; int c = Integer.parseInt(st.nextToken());
farm.get(a).add(new Pair(b,c)); farm.get(b).add(new Pair(a,c));
}
comp = new ArrayList<>(); visited = new boolean[num][num];
for (int i = 0;i<num;i++) {
if (!visited[i][0]) {
comp.add(new ArrayList<>()); comp.get(comp.size()-1).add(i);
visited[i][0] = true;
FindConnectedComponents(i);
}
}
for (int i = 0;i<num;i++) visited[i][0] = false;
int C = comp.size();
ArrayList<ArrayList<Integer>> dist = new ArrayList<>();
for (int i = 0;i<C;i++) {
dist.add(FindDist(comp.get(i)));
}
long[][] dp = new long[C][Y+1]; //Number of tracks using all the first i connected components and having track sum of j
long[][] ans = new long[C][Y+1]; //Sum of the lengths of the tracks in dp[i][j];
//Initial conditions
for (int dis : dist.get(0)) {
int j = Math.min(Y,dis+X);
dp[0][j] = (dp[0][j]+1)%mod; ans[0][j] = (ans[0][j]+dis+X)%mod;
}
//Forward DP
for (int i = 0;i<C-1;i++) {
for (int j = 0;j<=Y;j++) {
for (int l : dist.get(i+1)) {
long times = (dp[i][j]*(i+1)*2)%mod;
int next = Math.min(Y,j+l+X);
dp[i+1][next] = (dp[i+1][next]+times)%mod;
ans[i+1][next] = (ans[i+1][next]+(l+X)*times)%mod;
ans[i+1][next] = (ans[i+1][next]+ans[i][j]*(i+1)*2)%mod;
}
}
}
System.out.println(ans[C-1][Y]);
}
//Finding the distance matrix for each tree/component
public static ArrayList<Integer> FindDist(ArrayList<Integer> comp) {
ArrayList<Integer> ans = new ArrayList<>();
for (int i : comp) {
int[] dist = new int[num]; Arrays.fill(dist,-1);
LinkedList<Integer> list = new LinkedList(); list.add(i); dist[i] = 0;
while (list.size()>0) {
int curr = list.poll();
for (Pair p : farm.get(curr)) {
if (dist[p.next]==-1) {
dist[p.next] = dist[curr]+p.w;
list.add(p.next);
}
}
}
for (int j = 0;j<num;j++) {
if (dist[j]==-1||dist[j]==0||visited[i][j]||visited[j][i]) continue;
ans.add(dist[j]); visited[i][j] = true;
}
}
return ans;
}
//Finding the connected components.
public static void FindConnectedComponents(int curr) {
for (Pair p : farm.get(curr)) {
if (!visited[p.next][0]) {
visited[p.next][0] = true;
comp.get(comp.size()-1).add(p.next);
FindConnectedComponents(p.next);
}
}
}
public static class Pair {
int next; int w;
public Pair (int next, int w) {
this.next = next; this.w = w;
}
}
}
```

Code explanation:

Basically, I first found the connect components of the given total farmland (comp represents these connected components). These connect components are the K different farms. Note that these farms are also each a tree. Then I used BFS to find the pairwise distances in each farm/tree (stored in dist in my code). Up to here I’m fairly confident my code works, but it wouldn’t hurt to look at it.

Next, I did a forward dp (the dp is defined in the code). The dp works by taking the newest connected component and adding it to one of the i+1 possible spots. Each addition has two directions hence the (i+1)*2. Then I update ans[i][j] with the extra distance that is added due to the new connect component.

Sorry if my explanation was bad. It’s my first time explaining code through text.