I was going through Usaco Guides Solution (here) for I Would Walk 500 Miles. The solution using Kruskals algorithm seemed to be way more complicated than it should be. My solution here is straightforward and ACs the problem, and all I had to do since it took up so much memory was changing some ints to short. Can someone look at this and perhaps change the usaco guide solution?
Note: I probably could have just used global variables for i and j, but the logic is still the same.
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <numeric>
#include <queue>
#include <stack>
#include <iomanip>
using namespace std;
void baseIO(string s = ""){
ios_base::sync_with_stdio(0);
cin.tie(0);
if (s.size()){
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
}
struct Edge{
short to, from;
int weight;
};
class DisjointSets {
private:
vector<short> parents;
vector<short> sizes;
public:
DisjointSets(short size) : parents(size), sizes(size, 1){
for (short i = 0; i < size; i++) parents[i] = i;
}
short find(short x) { return parents[x] == x ? x : (parents[x] = find(parents[x])); }
bool unite(short x, short y){
short x_root = find(x);
short y_root = find(y);
if (x_root == y_root) return false;
if (sizes[x_root] < sizes[y_root]) swap(x_root, y_root);
sizes[x_root] += sizes[y_root];
parents[y_root] = x_root;
return true;
}
bool connected(short x, short y) {return find(x) == find(y); }
};
int main() {
baseIO("walk");
short n, k;
cin >> n >> k;
vector<Edge> edges;
for (short i = 1; i <= n; i++){
for (short j = i + 1; j <= n; j++) edges.push_back({i, j, 2019201997 - 84 * i - 48 * j});
}
sort(edges.begin(), edges.end(), [](Edge &a, Edge &b){
return a.weight < b.weight;
});
DisjointSets dsu(n + 1);
short cnt = 0;
for (auto &e : edges){
if (dsu.unite(e.from, e.to)){
cnt++;
if (cnt == n - k + 1){
cout << e.weight << endl;
break;
}
}
}
return 0;
}