Optimizaciones del Compilador y Utilidades Base

Directivas de Optimización GCC

Para entornos de programación competitiva, se pueden aplicar directivas de preprocesador para forzar al compilador a generar código altamente optimizado, aprovechando instrucciones avanzadas del procesador.

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("inline,fgcse,fgcse-lm,ipa-sra,tree-pre,tree-vrp")
#pragma GCC optimize("fpeephole2,ffast-math,fsched-spec,unroll-loops")
#pragma GCC optimize("falign-jumps,falign-loops,falign-labels,fdevirtualize")
#pragma GCC optimize("fcaller-saves,fcrossjumping,fthread-jumps,whole-program")
#pragma GCC optimize("freorder-blocks,fschedule-insns,inline-functions")
#pragma GCC optimize("ftree-tail-merge,fschedule-insns2,fstrict-aliasing")
#pragma GCC optimize("fstrict-overflow,falign-functions,fcse-skip-blocks")
#pragma GCC optimize("fcse-follow-jumps,fsched-interblock,partial-inlining")
#pragma GCC optimize("no-stack-protector,freorder-functions,findirect-inlining")
#pragma GCC optimize("fhoist-adjacent-loads,frerun-cse-after-loop,inline-small-functions")
#pragma GCC optimize("ftree-switch-conversion,foptimize-sibling-calls")
#pragma GCC optimize("fexpensive-optimizations,funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once,fdelete-null-pointer-checks")

Macros y Definiciones Útiles

Definiciones abreviadas para reducir la verbosidad del código y acelerar la escirtura durante las competiciones.

#define REG register
#define INLINE __attribute__((always_inline)) inline
#define LEFT_CHILD(node) ((node) << 1)
#define RIGHT_CHILD(node) ((node) << 1 | 1)
#define LOWEST_BIT(x) ((x) & -(x))
#define PAIR_INT std::pair<int, int>
#define MAKE_PAIR std::make_pair
#define FIRST_ELEMENT first
#define SECOND_ELEMENT second
#define CLEAR_ARRAY(arr) memset(arr, 0, sizeof(arr))
#define INT64 long long
#define FLOAT80 long double
#define PI acos(-1.0)

Entrada y Salida Rápida (Fast I/O)

Imlpementación de lectura y escritura mediante buffers para minimizar la sobrecarga de las funciones estándar de E/S.

const int BUFFER_SIZE = 1 << 20;
char io_buffer[BUFFER_SIZE], *io_head = io_buffer, *io_tail = io_buffer;

INLINE char read_char() {
    if (io_head == io_tail) {
        io_tail = (io_head = io_buffer) + fread(io_buffer, 1, BUFFER_SIZE, stdin);
        if (io_head == io_tail) return EOF;
    }
    return *io_head++;
}

template <typename T>
INLINE void read_int(T &value) {
    value = 0;
    int sign = 1;
    char ch = read_char();
    while (ch < '0' || ch > '9') {
        if (ch == '-') sign = -1;
        ch = read_char();
    }
    while (ch >= '0' && ch <= '9') {
        value = (value << 3) + (value << 1) + (ch ^ 48);
        ch = read_char();
    }
    value *= sign;
}

template <typename T>
INLINE void write_int(T value) {
    if (value < 0) {
        putchar('-');
        value = ~value + 1;
    }
    if (value > 9) write_int(value / 10);
    putchar((value % 10) ^ 48);
}

Algoritmos de Caminos Más Cortos

Algoritmo de Floyd-Warshall

Encuentra los caminos más cortos entre todos los pares de vértices en un grafo ponderado. Complejidad temporal: O(V^3).

const int MAXV = 505;
const int INF = 0x3f3f3f3f;
int num_vertices, num_edges;
int dist_matrix[MAXV][MAXV];

void compute_floyd() {
    read_int(num_vertices); read_int(num_edges);
    memset(dist_matrix, 0x3f, sizeof(dist_matrix));
    for (int i = 1; i <= num_vertices; ++i) dist_matrix[i][i] = 0;

    for (int i = 0; i < num_edges; ++i) {
        int u, v, w;
        read_int(u); read_int(v); read_int(w);
        dist_matrix[u][v] = dist_matrix[v][u] = std::min(dist_matrix[u][v], w);
    }

    for (int k = 1; k <= num_vertices; ++k) {
        for (int i = 1; i <= num_vertices; ++i) {
            for (int j = 1; j <= num_vertices; ++j) {
                if (i != j && i != k && j != k && dist_matrix[i][k] != INF) {
                    dist_matrix[i][j] = std::min(dist_matrix[i][j], dist_matrix[i][k] + dist_matrix[k][j]);
                }
            }
        }
    }
}

Algoritmo de Dijkstra

Dijkstra Estándar

Ideal para grafos densos. Complejidad temporal: O(V^2).

struct GraphEdge {
    int target, weight;
};
std::vector<GraphEdge> adj_list[MAXV];
int min_dist[MAXV];
bool is_visited[MAXV];

void dijkstra_standard(int source) {
    for (int i = 1; i <= num_vertices; ++i) min_dist[i] = INF;
    min_dist[source] = 0;

    for (int iter = 1; iter < num_vertices; ++iter) {
        int closest_node = -1;
        int shortest_dist = INF;
        for (int i = 1; i <= num_vertices; ++i) {
            if (!is_visited[i] && min_dist[i] < shortest_dist) {
                shortest_dist = min_dist[i];
                closest_node = i;
            }
        }
        if (closest_node == -1) break;
        is_visited[closest_node] = true;

        for (const auto &edge : adj_list[closest_node]) {
            int next_node = edge.target;
            if (!is_visited[next_node] && min_dist[next_node] > shortest_dist + edge.weight) {
                min_dist[next_node] = shortest_dist + edge.weight;
            }
        }
    }
}

Dijkstra con Cola de Prioridad

Optimizado para grafos dispersos. Complejidad temporla: O((V + E) log V).

void dijkstra_heap(int source) {
    memset(min_dist, 0x3f, sizeof(min_dist));
    min_dist[source] = 0;
    std::priority_queue<PAIR_INT, std::vector<PAIR_INT>, std::greater<PAIR_INT>> pq;
    pq.push(MAKE_PAIR(0, source));

    while (!pq.empty()) {
        auto [current_dist, u] = pq.top();
        pq.pop();

        if (is_visited[u]) continue;
        is_visited[u] = true;

        for (const auto &edge : adj_list[u]) {
            int v = edge.target;
            if (min_dist[v] > current_dist + edge.weight) {
                min_dist[v] = current_dist + edge.weight;
                if (!is_visited[v]) {
                    pq.push(MAKE_PAIR(min_dist[v], v));
                }
            }
        }
    }
}

Algoritmo de Bellman-Ford y SPFA

Bellman-Ford Estándar

Capaz de detectar ciclos negativos. Complejidad temporal: O(V * E).

struct DirectedEdge {
    int from, to, weight;
};
std::vector<DirectedEdge> edge_list;
int bf_dist[MAXV];

bool bellman_ford(int source) {
    memset(bf_dist, 0x3f, sizeof(bf_dist));
    bf_dist[source] = 0;
    bool updated = false;

    for (int i = 1; i <= num_vertices; ++i) {
        updated = false;
        for (const auto &e : edge_list) {
            if (bf_dist[e.from] != INF && bf_dist[e.to] > bf_dist[e.from] + e.weight) {
                bf_dist[e.to] = bf_dist[e.from] + e.weight;
                updated = true;
            }
        }
        if (!updated) break;
    }
    return updated;
}

SPFA (Shortest Path Faster Algorithm)

Variante con cola para detectar ciclos negativos de forma más eficiente en la práctica. Complejidad temporal promedio: O(E), peor caso: O(V * E).

int spfa_dist[MAXV], visit_count[MAXV];
bool in_queue[MAXV];

bool spfa(int source) {
    memset(spfa_dist, 0x3f, sizeof(spfa_dist));
    spfa_dist[source] = 0;
    in_queue[source] = true;
    std::queue<int> q;
    q.push(source);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_queue[u] = false;

        for (const auto &edge : adj_list[u]) {
            int v = edge.target;
            if (spfa_dist[v] > spfa_dist[u] + edge.weight) {
                spfa_dist[v] = spfa_dist[u] + edge.weight;
                visit_count[v] = visit_count[u] + 1;
                if (visit_count[v] >= num_vertices) return false;
                if (!in_queue[v]) {
                    q.push(v);
                    in_queue[v] = true;
                }
            }
        }
    }
    return true;
}

Árbol de Expansión Mínima (MST)

Algoritmo de Kruskal

Utiliza la estructura de datos Conjuntos Disjuntos (DSU). Complejidad temporal: O(E log E).

const int MAXE = 200005;
struct MSTEdge {
    int u, v, w;
} mst_edges[MAXE];
int parent_uf[MAXV];

int find_set(int x) {
    return parent_uf[x] == x ? x : parent_uf[x] = find_set(parent_uf[x]);
}

void kruskal() {
    int total_weight = 0, edges_added = 0;
    for (int i = 1; i <= num_vertices; ++i) parent_uf[i] = i;

    std::sort(mst_edges + 1, mst_edges + 1 + num_edges, [](const MSTEdge &a, const MSTEdge &b) {
        return a.w < b.w;
    });

    for (int i = 1; i <= num_edges; ++i) {
        int root_u = find_set(mst_edges[i].u);
        int root_v = find_set(mst_edges[i].v);
        if (root_u != root_v) {
            parent_uf[root_u] = root_v;
            total_weight += mst_edges[i].w;
            if (++edges_added == num_vertices - 1) break;
        }
    }
    printf("%d\n", total_weight);
}

Algoritmo de Prim

Prim Estándar

Adecuado para grafos densos. Complejidad temporal: O(V^2).

void prim_standard() {
    int current_node = 1, nodes_added = 1, total_weight = 0;
    memset(min_dist, 0x3f, sizeof(min_dist));

    while (nodes_added < num_vertices) {
        for (const auto &edge : adj_list[current_node]) {
            int v = edge.target;
            if (!is_visited[v] && min_dist[v] > edge.weight) {
                min_dist[v] = edge.weight;
            }
        }

        int shortest_edge = INF;
        int next_node = -1;
        ++nodes_added;
        is_visited[current_node] = true;

        for (int i = 1; i <= num_vertices; ++i) {
            if (!is_visited[i] && min_dist[i] < shortest_edge) {
                shortest_edge = min_dist[i];
                next_node = i;
            }
        }
        total_weight += shortest_edge;
        current_node = next_node;
    }
    printf("%d\n", total_weight);
}

Prim con Cola de Prioridad

Optimizado para grafos dispersos. Complejidad temporal: O((V + E) log V).

void prim_heap() {
    int total_weight = 0, nodes_added = 0;
    memset(min_dist, 0x3f, sizeof(min_dist));
    min_dist[1] = 0;
    std::priority_queue<PAIR_INT, std::vector<PAIR_INT>, std::greater<PAIR_INT>> pq;
    pq.push(MAKE_PAIR(0, 1));

    while (!pq.empty() && nodes_added < num_vertices) {
        auto [weight, u] = pq.top();
        pq.pop();

        if (is_visited[u]) continue;
        ++nodes_added;
        total_weight += weight;
        is_visited[u] = true;

        for (const auto &edge : adj_list[u]) {
            int v = edge.target;
            if (min_dist[v] > edge.weight) {
                min_dist[v] = edge.weight;
                pq.push(MAKE_PAIR(min_dist[v], v));
            }
        }
    }
    printf("%d\n", total_weight);
}

Ancestro Común Más Bajo (LCA)

Ascensión Binaria (Binary Lifting)

Preprocesamiento en O(V log V) y consultas en O(log V). Algoritmo en línea.

int up[MAXV][20], depth[MAXV];
std::vector<int> tree_adj[MAXV];

void dfs_lifting(int u, int p) {
    up[u][0] = p;
    depth[u] = depth[p] + 1;
    for (int i = 1; i < 20; ++i) {
        up[u][i] = up[up[u][i - 1]][i - 1];
    }
    for (int v : tree_adj[u]) {
        if (v != p) dfs_lifting(v, u);
    }
}

int query_lca_lifting(int u, int v) {
    if (depth[u] < depth[v]) std::swap(u, v);
    for (int i = 19; i >= 0; --i) {
        if (depth[u] - depth[v] >= (1 << i)) {
            u = up[u][i];
        }
    }
    if (u == v) return u;
    for (int i = 19; i >= 0; --i) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[v][0];
}

Descomposición en Cadenas Pesadas (Heavy-Light Decomposition)

Preprocesamiento en O(V) y consultas en O(log V). Algoritmo en línea.

int parent_hld[MAXV], depth_hld[MAXV], subtree_size[MAXV], heavy_child[MAXV];
int chain_top[MAXV];

void dfs_hld_size(int u, int p) {
    parent_hld[u] = p;
    depth_hld[u] = depth_hld[p] + 1;
    subtree_size[u] = 1;
    heavy_child[u] = -1;

    for (int v : tree_adj[u]) {
        if (v == p) continue;
        dfs_hld_size(v, u);
        subtree_size[u] += subtree_size[v];
        if (heavy_child[u] == -1 || subtree_size[v] > subtree_size[heavy_child[u]]) {
            heavy_child[u] = v;
        }
    }
}

void dfs_hld_chain(int u, int top_node) {
    chain_top[u] = top_node;
    if (heavy_child[u] != -1) {
        dfs_hld_chain(heavy_child[u], top_node);
    }
    for (int v : tree_adj[u]) {
        if (v != parent_hld[u] && v != heavy_child[u]) {
            dfs_hld_chain(v, v);
        }
    }
}

int query_lca_hld(int u, int v) {
    while (chain_top[u] != chain_top[v]) {
        if (depth_hld[chain_top[u]] < depth_hld[chain_top[v]]) std::swap(u, v);
        u = parent_hld[chain_top[u]];
    }
    if (depth_hld[u] > depth_hld[v]) std::swap(u, v);
    return u;
}

Tabla Dispersa con Recorrido Euleriano (Sparse Table)

Preprocesamiento en O(V log V) y consultas en O(1). Algoritmo en línea.

int sparse_table[MAXV << 1][21], euler_tour[MAXV << 1], first_occurrence[MAXV];
int tour_timer = 0;

int get_shallower(int x, int y) {
    return depth[x] < depth[y] ? x : y;
}

void dfs_euler(int u, int p) {
    euler_tour[++tour_timer] = u;
    first_occurrence[u] = tour_timer;
    for (int v : tree_adj[u]) {
        if (v != p) {
            dfs_euler(v, u);
            euler_tour[++tour_timer] = u;
        }
    }
}

int log_table[MAXV << 1];

void build_sparse_table() {
    log_table[0] = -1;
    for (int i = 1; i <= tour_timer; ++i) {
        log_table[i] = log_table[i >> 1] + 1;
    }
    for (int i = 1; i <= tour_timer; ++i) {
        sparse_table[i][0] = euler_tour[i];
    }
    for (int k = 1; (1 << k) <= tour_timer; ++k) {
        for (int i = 1; i + (1 << k) - 1 <= tour_timer; ++i) {
            sparse_table[i][k] = get_shallower(sparse_table[i][k - 1], sparse_table[i + (1 << (k - 1))][k - 1]);
        }
    }
}

int query_lca_sparse(int u, int v) {
    if (u == v) return u;
    int left = first_occurrence[u];
    int right = first_occurrence[v];
    if (left > right) std::swap(left, right);
    int k = log_table[right - left + 1];
    return get_shallower(sparse_table[left][k], sparse_table[right - (1 << k) + 1][k]);
}