Problem A: Road Construction

Description

There are n initially isolated cities. In each round, every city connects to its nearest neighbor. If a cycle formss during a round, the shortest edge in that cycle is removed. Once cities are connected, they form a "union" and act as a single entity in subsequent rounds. The process continues until the entire graph is connected.

Solution

It can be observed that since every city connects to its nearest neighber, any cycle formed will have equal edge weights. Since already connected components cannot connect to each other again, the final result is always a tree. Therefore, we simply need to find the Minimum Spanning Tree (MST). Due to potential memory constraints with adjacency matrices, Prim's algorithm is preferred over Kruskal's for this scenario.

Code

#include <bits/stdc++.h>
#define MAXN 5005
#define ll long long
using namespace std;

int n, visited[MAXN];
double totalCost, minDist[MAXN];
int coordX[MAXN], coordY[MAXN];

double calculateDistance(int i, int j) {
    ll dx = coordX[i] - coordX[j];
    ll dy = coordY[i] - coordY[j];
    return sqrt(dx * dx + dy * dy);
}

void primMST() {
    visited[1] = 1;
    for (int i = 2; i <= n; i++) {
        minDist[i] = calculateDistance(1, i);
    }

    for (int step = 1; step < n; step++) {
        double closest = 1e9;
        int nextCity = 0;
        
        for (int i = 1; i <= n; i++) {
            if (visited[i]) continue;
            if (minDist[i] < closest) {
                closest = minDist[i];
                nextCity = i;
            }
        }

        visited[nextCity] = 1;
        totalCost += closest;

        for (int i = 1; i <= n; i++) {
            if (!visited[i] && nextCity != i) {
                minDist[i] = min(minDist[i], calculateDistance(nextCity, i));
            }
        }
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> coordX[i] >> coordY[i];
    }
    primMST();
    printf("%.2lf", totalCost);
    return 0;
}

Problem B: Beast Path Management

Description

Given a graph with n nodes, edges are added one by one (w total). After each edge addition, output the weight of the current Minimum Spanning Tree. If the graph is not connected, output -1.

Solution

We can re-run Kruskal's algorithm after every edge insertion. Sort the edges added so far and apply the standard Union-Find logic to build the MST incrementally.

Code

#include <bits/stdc++.h>
#define MAXN 205
using namespace std;

int n, w, parent[MAXN];
struct Connection {
    int u, v, weight;
    bool operator<(const Connection& other) const {
        return weight < other.weight;
    }
} edges[6005];

int findRoot(int x) {
    if (x == parent[x]) return x;
    return parent[x] = findRoot(parent[x]);
}

int main() {
    cin >> n >> w;
    for (int i = 1; i <= w; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].weight;
        
        if (i < n - 1) {
            cout << "-1\n";
            continue;
        }

        for (int j = 1; j <= n; j++) parent[j] = j;
        
        sort(edges + 1, edges + 1 + i);
        
        int mstWeight = 0, edgeCount = 0;
        for (int j = 1; j <= i; j++) {
            int ru = findRoot(edges[j].u);
            int rv = findRoot(edges[j].v);
            if (ru == rv) continue;
            
            parent[ru] = rv;
            edgeCount++;
            mstWeight += edges[j].weight;
            if (edgeCount == n - 1) break;
        }
        
        if (edgeCount < n - 1) mstWeight = -1;
        cout << mstWeight << "\n";
    }
    return 0;
}

Problem C: Road Construction Upgrade

Description

There are n points and m edges. Each edge has two weights: type 1 and type 2 (where type 1 >= type 2). The goal is to find an MST that contains at least k edges of type 1.

Solution

Follow the Kruskal strategy in two phases. First, sort all edges by their type 1 weight and add edges until exactly k type 1 edges are in the MST. Then, sort the remaining edges by their type 2 weight and continue building the MST until n-1 edges are selected.

Code

#include <bits/stdc++.h>
#define MAXN 10005
using namespace std;

int n, m, k, totalCost, parent[MAXN], selectedCount, ptr;
vector<pair<int, int>> selectedEdges;
struct Road {
    int u, v, w1, w2, id;
} data[20005];

bool sortByW1(Road a, Road b) { return a.w1 == b.w1 ? a.w2 > b.w2 : a.w1 < b.w1; }
bool sortByW2(Road a, Road b) { return a.w2 < b.w2; }

int find(int x) {
    if (x == parent[x]) return x;
    return parent[x] = find(parent[x]);
}

int main() {
    cin >> n >> k >> m;
    m--; // adjust for 0-index or specific input constraint
    for (int i = 1; i <= n; i++) parent[i] = i;
    
    for (int i = 1; i <= m; i++) {
        cin >> data[i].u >> data[i].v >> data[i].w1 >> data[i].w2;
        data[i].id = i;
    }
    
    sort(data + 1, data + 1 + m, sortByW1);
    
    // Phase 1: Select k type-1 edges
    for (int i = 1; i <= m; i++) {
        int ru = find(data[i].u);
        int rv = find(data[i].v);
        if (ru == rv) continue;
        
        parent[ru] = rv;
        totalCost = data[i].w1;
        selectedCount++;
        selectedEdges.push_back({data[i].id, 1});
        
        if (selectedCount == k) {
            ptr = i + 1;
            break;
        }
    }
    
    // Phase 2: Select remaining edges by type-2 weight
    sort(data + ptr, data + 1 + m, sortByW2);
    for (int i = ptr; i <= m; i++) {
        int ru = find(data[i].u);
        int rv = find(data[i].v);
        if (ru == rv) continue;
        
        parent[ru] = rv;
        totalCost = max(totalCost, data[i].w2);
        selectedCount++;
        selectedEdges.push_back({data[i].id, 2});
        
        if (selectedCount == n - 1) break;
    }
    
    cout << totalCost << "\n";
    sort(selectedEdges.begin(), selectedEdges.end());
    for (int i = 0; i < n - 1; i++) {
        cout << selectedEdges[i].first << " " << selectedEdges[i].second << "\n";
    }
    return 0;
}

Problem D: Defeat Them One by One

Description

Given a tree with n nodes, removing an edge has a cost. There are k enemy-occupied nodes. Find the minimum cost to disconnect the tree so that no two enemy nodes are in the same connected component.

Solution

Invert the problem: instead of cutting edges, build a forest starting with no edges. We want k trees, each containing exactly one enemy node. Use a Max-Weight Kruskal approach (remove heaviest edges first). Keep track of whether a component contains an enemy. Only merge two components if at most one contains an enemy.

Code

#include <bits/stdc++.h>
#define int long long
#define MAXN 200005
using namespace std;

int n, m, hasEnemy[MAXN], parent[MAXN], result;
struct TreeEdge {
    int u, v, cost;
    bool operator<(const TreeEdge& x) const {
        return cost > x.cost; // sort descending
    }
} edges[MAXN];

int findSet(int x) {
    if (x == parent[x]) return x;
    return parent[x] = findSet(parent[x]);
}

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) parent[i] = i;
    
    for (int i = 1; i <= m; i++) {
        int x; cin >> x;
        hasEnemy[x] = 1;
    }
    
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges[i] = {u, v, w};
        result += w; // start with total weight, subtract what we keep
    }
    
    sort(edges + 1, edges + n);
    
    for (int i = 1; i < n; i++) {
        int ru = findSet(edges[i].u);
        int rv = findSet(edges[i].v);
        if (ru == rv) continue;
        
        // Cannot merge if both have enemies
        if (hasEnemy[ru] && hasEnemy[rv]) continue;
        
        parent[ru] = rv;
        hasEnemy[rv] |= hasEnemy[ru];
        result -= edges[i].cost; // we keep this edge, so we don't pay the cut cost
    }
    
    cout << result;
    return 0;
}

Problem E: I Would Walk 500 Miles G

Description

Given n cows, divide them into k groups. The distance between groups is defined by a specific formula. Maximize the minimum distance between any two groups.

Solution

Invert the problem. Building n-k edges connects nodes into k groups. We want to maximize the minimum edge weight in the MST, which is equivalent to finding the weight of the (n-k+1)-th edge added in Kruskal's algorithm.

Code

#include <bits/stdc++.h>
#define MAXN 7505
#define ll long long
#define X 2019201913
#define Y 2019201949
#define MOD 2019201997
using namespace std;

int n, k, edgesCount, parent[MAXN];
struct Link {
    int u, v;
    ll weight;
    bool operator<(const Link x) const {
        return weight < x.weight;
    }
} links[MAXN * MAXN / 2];

int find(int x) {
    if (x == parent[x]) return x;
    return parent[x] = find(parent[x]);
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) parent[i] = i;
    
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            ++edgesCount;
            links[edgesCount].u = i;
            links[edgesCount].v = j;
            links[edgesCount].weight = ((ll)i * X + (ll)j * Y) % MOD;
        }
    }
    
    sort(links + 1, links + 1 + edgesCount);
    
    int connected = 0;
    for (int i = 1; i <= edgesCount; i++) {
        if (connected == n - k) break; // We only need n-k edges
        
        int ru = find(links[i].u);
        int rv = find(links[i].v);
        if (ru == rv) continue;
        
        parent[ru] = rv;
        connected++;
    }
    
    // The answer is the weight of the next edge that would connect two components
    for (int i = 1; i <= edgesCount; i++) {
        if (find(links[i].u) != find(links[i].v)) {
            cout << links[i].weight;
            return 0;
        }
    }
    return 0;
}

Problem F: Grid Graph MST

Description

Given an n x m grid. Horizontal edges in row i cost a[i], and vertical edges in column j cost b[j]. Find the MST of this grid.

Solution

Adding edges one by one is inefficient. Since edges in the same row/column share costs, sort the rows and columns by cost. When adding a row of cost c, we can add multiple edges at once, but we must subtract edges that would form cycles. If k vertical lines are already present, adding a horizontal line creates m - k new edges (minus one if no horizontals added yet).

Code

#include <bits/stdc++.h>
#define MAXN 300005
#define int long long
using namespace std;

int n, m, edgeCount, total, idxH, idxV;
struct Item {
    int id, val;
    bool operator<(const Item a) const {
        return val < a.val;
    }
} rows[MAXN], cols[MAXN];

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> rows[i].val;
        rows[i].id = i;
    }
    for (int i = 1; i <= m; i++) {
        cin >> cols[i].val;
        cols[i].id = i;
    }
    
    sort(rows + 1, rows + 1 + n);
    sort(cols + 1, cols + 1 + m);
    
    rows[n+1].val = cols[m+1].val = 1e18;
    
    int addedEdges = 0;
    int hPtr = 0, vPtr = 0;
    
    while ((hPtr < n || vPtr < m) && addedEdges < n * m - 1) {
        if (rows[hPtr+1].val < cols[vPtr+1].val) {
            hPtr++;
            if (hPtr > 1) {
                int available = m - vPtr;
                if (vPtr == 0) available--;
                if (addedEdges + available <= n * m - 1) {
                    total += available * rows[hPtr].val;
                    addedEdges += available;
                } else {
                    total += (n * m - 1 - addedEdges) * rows[hPtr].val;
                    addedEdges = n * m - 1;
                }
            } else {
                if (addedEdges + m - 1 <= n * m - 1) {
                    total += (m - 1) * rows[hPtr].val;
                    addedEdges += m - 1;
                } else {
                    total += (n * m - 1 - addedEdges) * rows[hPtr].val;
                    addedEdges = n * m - 1;
                }
            }
        } else {
            vPtr++;
            if (vPtr > 1) {
                int available = n - hPtr;
                if (hPtr == 0) available--;
                if (addedEdges + available <= n * m - 1) {
                    total += available * cols[vPtr].val;
                    addedEdges += available;
                } else {
                    total += (n * m - 1 - addedEdges) * cols[vPtr].val;
                    addedEdges = n * m - 1;
                }
            } else {
                if (addedEdges + n - 1 <= n * m - 1) {
                    total += (n - 1) * cols[vPtr].val;
                    addedEdges += n - 1;
                } else {
                    total += (n * m - 1 - addedEdges) * cols[vPtr].val;
                    addedEdges = n * m - 1;
                }
            }
        }
    }
    cout << total;
    return 0;
}

Problem G: The Connectivity Game

Description

Two players play a game asking about direct connections between pairs of n cities. The responder (Jianjia) can adapt answers dynamically. The goal is to ensure the connectivity of the graph is only determined after the very last question is asked.

Solution

To delay knowing connectivity, the graph should remain disconnected (split into two components) for as long as possible. By processing the questions in reverse order and building the MST backwards (answering "Yes" to the latest possible edges), we ensure the graph becomes connected only at the very end. Answer "1" for edges included in the reverse MST, "0" otherwise.

Code

#include <bits/stdc++.h>
#define MAXQ 1150005
using namespace std;

int n, q, u, v, parent[MAXQ], response[MAXQ];
struct Query {
    int u, v, idx;
    bool operator<(const Query x) {
        return idx > x.idx; // Process in reverse order of asking
    }
} queries[MAXQ];

int find(int x) {
    if (x == parent[x]) return x;
    return parent[x] = find(parent[x]);
}

int main() {
    cin >> n;
    q = n * (n - 1) / 2;
    for (int i = 1; i <= q; i++) {
        cin >> u >> v;
        queries[i] = {u, v, i};
    }
    
    sort(queries + 1, queries + 1 + q);
    
    for (int i = 0; i < n; i++) parent[i] = i;
    
    for (int i = 1; i <= q; i++) {
        int ru = find(queries[i].u);
        int rv = find(queries[i].v);
        if (ru == rv) continue;
        
        parent[ru] = rv;
        response[queries[i].idx] = 1; // Answer "Yes" to these
    }
    
    for (int i = 1; i <= q; i++) cout << response[i] << "\n";
    return 0;
}

Problem H: Kuglarz (Cups)

Description

There are n cups. Paying cost c[i][j] tells you the parity of balls under cups i through j. Find the minimum cost to determine the parity of every single cup.

Solution

We can model intervals as edges between nodes. Using half-open intervals [i, j), knowing [i, k) and [k, j) implies knowing [i, j). To know every cup (i, i+1), we need nodes 0 to n to be connected. The cost is the sum of edges in the MST connecting nodes 0 through n (total n edges).

Code

#include <bits/stdc++.h>
#define int long long
#define MAXV 2005
using namespace std;

int n, cost, edgeCount, parent[MAXV], totalCost;
struct Interval {
    int u, v, w;
    bool operator<(const Interval x) const {
        return w < x.w;
    }
} intervals[MAXV * MAXV / 2];

int find(int x) {
    if (x == parent[x]) return x;
    return parent[x] = find(parent[x]);
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            cin >> cost;
            intervals[++edgeCount] = {i, j + 1, cost};
        }
    }
    
    for (int i = 1; i <= n + 1; i++) parent[i] = i;
    
    sort(intervals + 1, intervals + 1 + edgeCount);
    
    int edgesUsed = 0;
    for (int i = 1; i <= edgeCount; i++) {
        int ru = find(intervals[i].u);
        int rv = find(intervals[i].v);
        if (ru == rv) continue;
        
        parent[ru] = rv;
        totalCost += intervals[i].w;
        edgesUsed++;
        if (edgesUsed == n) break;
    }
    
    cout << totalCost;
    return 0;
}

Problem J: Tree I (White and Black Edges)

Description

Given a graph with black and white edges, find the MST that contains exactly need white edges.

Solution

Use binary search on a penalty value mid added to all white edges. Sort edges (resolving ties by preferring white edges if weights are equal). Run Kruskal. If the number of white edges in the MST is >= need, the penalty is too low (or just right). Adjust the binary search. Since the solution is guaranteed, if we have more white edges than needed but the weight matches, it's valid due to tie-breaking.

Code

#include <bits/stdc++.h>
#define MAXM 100005
using namespace std;

int n, m, need, lo, hi, finalAns, parent[MAXM];
struct GraphEdge {
    int u, v, w, color;
    bool operator<(const GraphEdge& other) const {
        if (w != other.w) return w < other.w;
        return color < other.color; // prefer white (0) over black (1) if tie
    }
} edges[MAXM];

int find(int x) {
    if (x == parent[x]) return x;
    return parent[x] = find(parent[x]);
}

int whiteCount, mstWeight;

void kruskal(int penalty) {
    whiteCount = mstWeight = 0;
    int edgesSelected = 0;
    
    for (int i = 1; i <= m; i++) {
        if (edgesSelected == n - 1) break;
        
        int ru = find(edges[i].u);
        int rv = find(edges[i].v);
        if (ru == rv) continue;
        
        parent[ru] = rv;
        edgesSelected++;
        mstWeight += edges[i].w;
        
        if (edges[i].color == 0) { // White edge
            whiteCount++;
            if (whiteCount <= need) {
                mstWeight -= penalty; // Subtract the penalty we added
            }
        }
    }
}

int main() {
    cin >> n >> m >> need;
    for (int i = 1; i <= m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w >> edges[i].color;
    }
    
    lo = -101, hi = 101;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        
        for (int i = 0; i < n; i++) parent[i] = i;
        for (int i = 1; i <= m; i++) if (edges[i].color == 0) edges[i].w += mid;
        
        sort(edges + 1, edges + 1 + m);
        kruskal(mid);
        
        if (whiteCount >= need) {
            finalAns = mstWeight;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
        
        // Restore original weights
        for (int i = 1; i <= m; i++) if (edges[i].color == 0) edges[i].w -= mid;
    }
    
    cout << finalAns;
    return 0;
}