(Analysis by Benjamin Qi)

Binary search on the answer $x$. For all wormholes $i$ such that $x\le w_i,$ draw an edge between barns $a_i$ and $b_i.$ It is possible to sort the cows with wormholes of width at least $x$ if and only if $p_i$ is in the same connected component as $i$ for all $i.$

To see that this is true, consider the case when the resulting edges form a tree. We can always perform swaps until one of the barns that is a leaf in the tree contains the correct cow. Then remove this leaf from the tree and continue the process.

Nick Wu's code:

import java.io.*;
import java.util.*;
public class wormsort {
public static void main(String[] args) throws IOException{
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
loc = new int[n];
component = new int[n];
for(int i = 0; i < n; i++) edges[i] = new LinkedList<>();
lhs = new int[m];
rhs = new int[m];
weight = new int[m];
for(int i = 0; i < n; i++) loc[i] = Integer.parseInt(st.nextToken())-1;
for(int i = 0; i < m; i++) {
int a = Integer.parseInt(st.nextToken())-1;
int b = Integer.parseInt(st.nextToken())-1;
int w = Integer.parseInt(st.nextToken());
}
br.close();
int minW = 0;
int maxW = 1000000001;
while(minW != maxW) {
int mid = (minW + maxW + 1) / 2;
if(valid(mid)) minW = mid;
else maxW = mid-1;
}
if(minW > 1e9) minW = -1;
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("wormsort.out")));
pw.println(minW);
pw.close();
}
static int[] loc, lhs, rhs, weight;
static int[] component;
private static void dfs(int curr, int label, int minW) {
if(component[curr] == label) return;
component[curr] = label;
for(Edge child: edges[curr]) if(child.w >= minW) dfs(child.d, label, minW);
}
private static boolean valid(int minW) {
Arrays.fill(component, -1);
int numcomps = 0;
for(int i = 0; i < component.length; i++) {
if(component[i] < 0) {
dfs(i, numcomps++, minW);
}
}
for(int i = 0; i < loc.length; i++) {
if(component[i] != component[loc[i]]) return false;
}
return true;
}
static class Edge {
int d, w;
public Edge(int d, int w) {
this.d = d;
this.w = w;
}
}
}