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.