# Connecting Two Barns

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;

//visited array for dfs
bool visited[maxn];

bool works(ll constraint) {
return true;
}

void init() {
for (ll i = 1; i <= n; i++) {
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++) {
}
}
}

//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;

}

//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.