USACO 2021 December Contest Silver Division - Connecting Two Barns

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We notice that we are actually given a graph with several connected components, and we want \(1\) and \(n\) to be in the same connected component by creating at most two new paths.

Thus, if \(1\) and \(n\) are in the same component from the start, the cost is \(0\), if not, we can directly connect the connected components they are in, taking the most optimal nodes, or through an intermediate connected component. We can remember for the connected component of \(n\) and \(1\) the elements, and for each node we remember the minimum cost of connecting a path with the connected component of \(1\), respectively that of \(n\).

Source code

The source code in C++ can be seen below.

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

using namespace std;

// given two components xa and xb, find the smallest cost between two edges which connects them
// you use binary search for this

long long findmin (int xa, int xb, vector<vector<int>> &whoo, vector<int> &components) {

    long long solx = (1LL<<60); 
    for (auto x : whoo[xa]) {
        int L = 0;
        int R = (int) whoo[components[xb] - 1].size() - 1;
        while (L <= R) {
            int mid = (L + R) / 2;
            solx = min(solx, 1LL * (x - whoo[components[xb] - 1][mid]) * (x - whoo[components[xb] - 1][mid]));
            if (mid + 1 < (int) whoo[components[xb] - 1].size()) {
                solx = min(solx, 1LL * (x - whoo[components[xb] - 1][mid+1]) * (x - whoo[components[xb] - 1][mid+1]));
            }
            if (whoo[components[xb] - 1][mid] <= x) {
                L = mid + 1;
            }
            else {
                R = mid - 1;
            }
        }
    }
    return solx;
}

void solve () {
    int n, m;
    cin >> n >> m;

    vector<int> components(n+1);
    vector<vector<int>> graph(n+1);
    vector<vector<int>> whoo;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    // do bfs to find connected components
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!components[i]) {
            queue<int> q;
            vector<int> vals;
            q.push(i);
            cnt++;
            components[i] = cnt;
            while (!q.empty()) {
                int node = q.front();
                vals.push_back(node);
                q.pop();
                for (auto x : graph[node]) {
                    if (!components[x]) {
                        q.push(x);
                        components[x] = cnt;
                    }
                }
            }
            sort(vals.begin(), vals.end());
            whoo.push_back(vals);
        }
    }

    // edge case
    if (components[1] == components[n]) {
        cout << 0 << '\n';
        return;
    }

    long long ans = (1LL<<60);

    // case 1 - connect 1 and n together with one move
    ans = min(ans, findmin(0, n, whoo, components));

    // case 2 - connect 1 with x and x with n (x is a component)
    for (int i = 1; i < (int) whoo.size(); i++) {
        if (i != components[n] - 1) {
            long long solxx = findmin(i, 1, whoo, components);
            long long solyy = findmin(i, n, whoo, components);
            ans = min(ans, solxx + solyy);
        }
    }

    cout << ans << '\n';
}

int main() {

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}