# Fenced In (Gold) TLE, RTE/MLE?

Hi, I am currently doing the USACO 2016 February gold contest, problem 3 Fenced In.
Since N is quite small, my idea is to create the graph and run an MST algorithm on it. I did it as follows, choosing to use Prim’s:

``````#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int V;
bool vis;

auto comp = [] (pair <int, int> first, pair <int, int> second) {
return first.second > second.second;
};

long long mst () {
int cost[V+1];
fill(cost+1, cost+1+V, 1e9+1);
cost = 0;
priority_queue <pair <int, int>, vector <pair <int, int>>, decltype(comp)> tmp(comp);
tmp.push(make_pair(1, 0));
while (!tmp.empty()) {
int cur = tmp.top().first;
tmp.pop();
if (!vis[cur]) {
vis[cur] = true;
for (pair <int, int> i : adjList[cur]) {
if (!vis[i.first] && cost[i.first] > i.second) {
cost[i.first] = i.second;
tmp.push(i);
}
}
}
}
long long totCost = 0;
for (int i = 1; i <= V; ++i) {
totCost += cost[i];
}
}

int main () {
//     freopen("fencedin.in", "r", stdin);
//     freopen("fencedin.out", "w", stdout);
int A, B, n, m;
cin >> A >> B >> n >> m;
V = (n+1)*(m+1);
int a[n+2], b[m+2];
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
a[n] = 0;
a[n+1] = A;
for (int i = 0; i < m; ++i) {
cin >> b[i];
}
b[m] = 0;
b[m+1] = B;
sort(a, a+n+2);
sort(b, b+m+2);
for (int i = 0; i < m+1; ++i) {
for (int j = 0; j < n+1; ++j) {
if (j != 0) {
}
if (j != n) {
}
if (i != m) {
}
if (i != 0) {
}
}
}
cout << mst();
}

``````

However, when I implemented the solution in C++, I passed the first 7 test cases but timed out on the 8th one and RTE/MLE on the last 2. I thought both my memory complexity is O(N^2) and my runtime complexity is O(N log N) (sorting) + O(N^2) (graph generation) + O(E log E) (Prim’s, where E is 4N^2) which is dominated by O(E log E). Theoretically, this should pass, but I don’t know where the problem is.

Can anyone point me out where it went wrong?
Thanks!

I had the same problem myself, and I feel like you’d be doing yourself a favor if you just switched to Kruskal’s. It seems Prim’s just doesn’t pair well with this problem.
As for why, well, I’m not really sure.

Thanks, Kruskal’s works!
I’m currently assuming that the problem for Prim’s was some memory issue, but it’ll be interesting to find out what the problem actually is.

1 Like