Hi, I am currently doing the USACO 2016 February gold contest, problem 3 Fenced In.
Link: Problem
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[4004002];
vector <pair <int, int>> adjList[4004002];
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[1] = 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];
}
return totCost;
}
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) {
adjList[i*(n+1)+j+1].push_back({i*(n+1)+j, b[i+1]-b[i]});
}
if (j != n) {
adjList[i*(n+1)+j+1].push_back({i*(n+1)+j+2, b[i+1]-b[i]});
}
if (i != m) {
adjList[i*(n+1)+j+1].push_back({(i+1)*(n+1)+j+1, a[j+1]-a[j]});
}
if (i != 0) {
adjList[i*(n+1)+j+1].push_back({(i-1)*(n+1)+j+1, a[j+1]-a[j]});
}
}
}
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!