barcos.cpp

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const int MAXK = 21;
const int INF = 0x3f3f3f3f;
array<vector<pair<int, int>>, MAXN> grafo;
array<array<int, MAXK>, MAXN> dp, dpMin;
array<int, MAXN> prof;
vector<int> pai, sub;

int find(int v) {return pai[v] = (pai[v] == v ? v : find(pai[v]));}
void une(int x, int y)
{
    x = find(x); y = find(y);
    if (x == y) return; //estao na mesma componente
    if (sub[x] < sub[y]) swap(sub[x], sub[y]);
    pai[y] = x;
    sub[x] += sub[y];
}

void dfs(int v, int p, int peso)
{
    prof[v] = prof[p] + 1;
    dp[v][0] = p; dpMin[v][0] = peso;
    for (int k = 1; k < MAXK; k++)
    {
        dp[v][k] = dp[dp[v][k-1]][k-1];
        dpMin[v][k] = min(dpMin[v][k-1], dpMin[dp[v][k-1]][k-1]);
    }

    for (auto [viz, vizP] : grafo[v])
    {
        if (viz == p) continue;
        dfs(viz, v, vizP);
    }
}

int calcPath(int x, int y)
{
    if (prof[x] < prof[y]) swap(x, y);
    int jump = prof[x] - prof[y], resp = INF;
    for (int k = 0; k < MAXK; k++) if (jump & (1 << k))
    {
        resp = min(resp, dpMin[x][k]);
        x = dp[x][k];
    }
    if (x == y) return resp;

    for (int k = MAXK-1; k >= 0; k--) if (dp[x][k] != dp[y][k])
    {
        resp = min({resp, dpMin[x][k], dpMin[y][k]});
        x = dp[x][k], y = dp[y][k];
    }

    return min({resp, dpMin[x][0], dpMin[y][0]});
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, B;
    cin >> N >> B;
    vector<tuple<int, int, int>> arestas(M); //peso, vertice 1, vertice 2
    for (auto &[p, x, y] : arestas)
        cin >> p >> x >> y;
    //Ordena as aretas por maior peso
    sort(arestas.rbegin(), arestas.rend());

    pai.resize(N+1); sub.resize(N+1); //Vetores do union-find da mst
    iota(pai.begin(), pai.end(), 0);
    fill(sub.begin(), sub.end(), 1);

    for (auto [p, x, y] : arestas)
    {
        if (find(x) == find(y)) continue; //aresta nao esta na mst
        une(x, y);
        //Adiciono a aresta
        grafo[x].emplace_back(y, p);
        grafo[y].emplace_back(x, p);
    }
    //Pre-calcula a sparse table
    dfs(1, 1, INF);
    int C;
    cin >> C;
    //Queries usando a sparse table e algoritmo de lca
    while (C--)
    {
        int X, Y;
        cin >> X >> Y;
        cout << calcPath(X, Y) << '\n';
    }
}

Belo código.

binga