100% sure about the overarching Logic.
USACO 2021 December Silver, Connecting Two Barns - if you can find the error in my code, you are officially a legend.
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
typedef long long ll;
using namespace std;
const int MX = 100005; const long long MOD = 1000000007;
//failed code because of an edge case causing an infinite loop
int visited[MX], ccc = 0, idx = 0;
vectoradj[MX], b1, bN, bV[MX];
void dfs(int cur, int g) {
visited[cur] = 1;
if(g == 1) b1.push_back(cur);
else if(g == 2) bN.push_back(cur);
else if(g == 3) bV[idx].push_back(cur);
FOR(i, 0, adj[cur].size()) {
int nxt = adj[cur][i];
if(!visited[nxt]) {
dfs(nxt, g);
}
}
}
int binarySearch(int target, vectorv) {
int lo = 0, hi = v.size(), min_dist = 2e9;
while(lo <= hi) {
int mid = (lo + hi) / 2;
if(v[mid] < target) {
if(pow(v[mid] - target, 2) < min_dist) min_dist = pow(v[mid] - target, 2);
lo = mid + 1;
}
else {
if(pow(v[mid] - target, 2) < min_dist) min_dist = pow(v[mid] - target, 2);
hi = mid - 1;
}
}
return min_dist;
}
int main(void) {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tt;
cin >> tt;
while(tt–) {
int n, m;
cin >> n >> m;
FOR(i, 0, m) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
//finding number of groups
FOR(i, 1, n + 1) {
if(!visited[i]) {
dfs(i, 0);
ccc++;
}
}
memset(visited, 0, sizeof(visited));
//no connections needed
if(ccc == 1) {
cout << "0\n";
break;
}
//2 connected components
else if(ccc == 2) {
int Min = 2e9;
//separate into groups
dfs(1, 1); //start from 1, store in vector 1
dfs(n, 2); //start from n, store in vector 2
sort(b1.begin(), b1.end());
sort(bN.begin(), bN.end());
//binary search
FOR(i, 0, b1.size()) Min = min(binarySearch(b1[i], bN) , Min); //b1 and bN
//cout << "cost: ";
cout << Min << "\n";
//cout << "\n";
}
//3+ connected components
else if(ccc >= 3) {
int Min1 = 2e9, Min2 = 2e9, Min3 = 2e9;
//separate into groups
dfs(1, 1);
dfs(n, 2);
idx = 0;
FOR(i, 1, n + 1) {
if(!visited[i]) {
dfs(i, 3);
idx++;
}
}
sort(b1.begin(), b1.end());
sort(bN.begin(), bN.end());
FOR(i, 0, idx) sort(bV[i].begin(), bV[i].end());
//binary search
FOR(i, 0, b1.size()) Min1 = min(binarySearch(b1[i], bN) , Min1); //b1 and bN
FOR(i, 0, b1.size()) {
FOR(j, 0, idx) Min2 = min(binarySearch(b1[i], bV[j]), Min2); //b1 and bV
}
FOR(i, 0, bN.size()) {
FOR(j, 0, idx) Min3 = min(binarySearch(bN[i], bV[j]), Min3); //bN and bV
}
cout << min(Min1, Min2 + Min3) << "\n";
}
//reset
memset(visited, 0, sizeof(visited));
b1.clear();
bN.clear();
FOR(i, 0, idx) bV[i].clear();
FOR(i, 1, n + 1) adj[i].clear();
ccc = 0;
}
}