USACO Open 2019 Gold - I Would Walk 500 Miles

Solution 1

$O(N^2)$ Prim's is intended; check the analysis.

Solution 2

Kruskal with two iterations of counting sort passes in 1966 ms ...

const int a = 2019201997-2019201913;
const int b = 2019201997-2019201949;

int N,K;

pi rhsh(int x) { return {x>>16,x&((1<<16)-1)}; }
int wei(int x) { return (x>>16)*a+(x&((1<<16)-1))*b; }

/**
 * Description: Disjoint Set Union with path compression

Solution 3

Do a little math.