Problem Link: USACO

I understand the official algorithm, but my previous algorithm timed out despite being similar to the official solution.

My previous algorithm timed out for the last 5 test cases. Here’s a description: Get all the connected components using dfs. Then for each of the connected components, use binary search to get the closest distance from that component to the component with farm 1 and from the component containing farm n.

I don’t understand why this times out even though I am presumably checking n nodes.

Your algorithm seems correct. Could you paste your code? Would make it easier to debug(How to ask for help on a problem)

Are you sure about that? A common mistake on the binary search is which array you’re binary searching on… Check my code here for more information on how to do this.

I am in the process of commenting my code. I will share it with you alll soon.

Edit:

```
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <string>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 10;
const ll zer = 0;
const ll bignumber = 9999999999999;
//input
ll n, m;
//adjacency list
vector <ll> adj[maxn];
//visited array for dfs
bool visited[maxn];
bool works(ll constraint) {
return true;
}
//clear adjacency list and visited
void init() {
for (ll i = 1; i <= n; i++) {
adj[i].clear();
visited[i] = false;
}
}
//stores the connected components
vector <vector <ll>> cc;
//stores the ids of each of the nodes
ll id[maxn];
//used to get the connected components
vector <ll> temp;
//self-explanatory dfs
void dfs(ll node) {
for (ll k = 0; k < adj[node].size(); k++) {
if (!visited[adj[node][k]]) {
visited[adj[node][k]] = true;
temp.push_back(adj[node][k]);
dfs(adj[node][k]);
}
}
}
//computes the ID of each of the n nodes
void computeID() {
for (ll k = 0; k < cc.size(); k++) {
for (ll i = 0; i < cc[k].size(); i++) {
id[cc[k][i]] = k;
}
}
}
void floodfill() {
//clear everything from previous test cases
cc.clear();
temp.clear();
for (ll i = 1; i <= n; i++) id[i] = -1;
//get the connected components and build cc
for (ll i = 1; i <= n; i++) {
if (!visited[i]) {
visited[i] = true;
temp.push_back(i);
dfs(i);
sort(temp.begin(), temp.end());
cc.push_back(temp);
temp.clear();
}
}
//compute the IDs of each of the n nodes
computeID();
}
//since lower bound returns the first index >=, I might need the returned index or the returned index minus 1 (if possible)
//a and b are the ids of two connected components
ll calculateCost(ll a, ll b) {
//If they are the same component, return 0
if (a == b) {
return 0;
}
//set ret to a big number
ll ret = bignumber;
//traverse the array with smaller size
if (cc[a] > cc[b]) {
swap(a, b);
}
//check each element of cc[a] and binary search on cc[b]
for (ll k = 0; k < cc[a].size(); k++) {
ll index1 = lower_bound(cc[b].begin(), cc[b].end(), cc[a][k]) - cc[b].begin();
ll index2 = index1 - 1;
if (index1 >= 0 && index1 < cc[b].size()) {
ret = min(ret, (cc[b][index1] - cc[a][k]) * (cc[b][index1] - cc[a][k]));
}
if (index2 >= 0 && index2 < cc[b].size()) {
ret = min(ret, (cc[b][index2] - cc[a][k]) * (cc[b][index2] - cc[a][k]));
}
}
return ret;
}
void solve()
{
cin >> n >> m;
init();
for (ll i = 0; i < m; i++) {
ll a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
//get the cc's
floodfill();
//If 1 and N are in the same component, print 1
if (id[1] == id[n]) {
cout << 0 << endl;
return;
}
//This covers the case where only one path is built
ll ans = calculateCost(id[1], id[n]);
//pick all middle components and get the cost
for (ll middle = 0; middle < cc.size(); middle++) {
ll cost1 = calculateCost(id[1], middle);
ll cost2 = calculateCost(middle, id[n]);
ll totalcost = cost1 + cost2;
ans = min(ans, totalcost);
}
cout << ans << endl;
}
int main()
{
//init();
//do all test cases
ll t;
cin >> t;
while (t--) {
solve();
}
}
```

1 Like

Have you tried stress testing it?

I tried using the code in the usaco guide solution but it only passed the first 5 test cases.

Please see the updated code on the same link provided.

It worked. All I had to do was to make sure that I was binary searching on the larger component