contestlib

A collection of competitive programming templates and algorithms in C++.

Repository Structure

Data Structures (datastruct/)

• dsu.cpp: Disjoint Set Union (Union-Find) with path compression and union by size
• fen.cpp: Fenwick Tree (Binary Indexed Tree) for prefix sum queries
• hasher.cpp: String hashing utilities
• indexed_set.cpp: Ordered set with index-based queries
• lazy_seg_tree.cpp: Segment tree with lazy propagation
• lichao.cpp: Li Chao tree for maintaining convex hull of lines
• linear_rmq.cpp: Linear-time RMQ preprocessing
• monotonic_queue.cpp: Monotonic queue for sliding window problems
• rmq.cpp: Range Minimum Query with sparse table
• seg_tree.cpp: Standard segment tree implementation
• short_lazy_seg_tree.cpp: Compact lazy segment tree
• short_rmq.cpp: Compact RMQ implementation
• treap.cpp: Treap (randomized binary search tree)

Graph Algorithms (graph/)

• bellman_ford.cpp: Bellman-Ford shortest path algorithm (handles negative edges)
• bridges_art.cpp: Bridges and Articulation Points
• floyd_warshall.cpp: Floyd-Warshall all-pairs shortest path algorithm
• binary_lifting_lca.cpp: Lowest Common Ancestor using binary lifting
• centroid.cpp: Centroid decomposition
• dijkstra.cpp: Dijkstra's shortest path algorithm
• dinic.cpp: Dinic's algorithm for maximum flow
• hld.cpp: Heavy-Light Decomposition
• lca.cpp: Lowest Common Ancestor
• linear_lca.cpp: Linear-time LCA preprocessing
• mst.cpp: Minimum Spanning Tree using Kruskal's algorithm
• scc.cpp: Strongly Connected Components using Kosaraju's algorithm
• toposort.cpp: Topological sort for directed acyclic graphs (DAG)

Math (math/)

• fact.cpp: Factorial and combinatorics utilities
• mod_int.cpp: Modular arithmetic with automatic modulo operations

String Algorithms (string/)

• aho_corasick.cpp: Aho-Corasick automaton for multi-pattern matching
• kmp.cpp: KMP (Knuth-Morris-Pratt) pattern matching algorithm
• zalgo.cpp: Z-algorithm for linear-time string matching

Miscellaneous (misc/)

• bins.cpp: Binary search utilities
• compress_inplace.cpp: In-place coordinate compression
• compress.cpp: Coordinate compression
• fast_input.cpp: Fast I/O for competitive programming
• rand.cpp: Random number generation utilities
• timer.cpp: Timing and benchmarking utilities
• vec.cpp: Vector utilities and shortcuts

Usage

Each file is a self-contained implementation that can be copied directly into your solution. Most implementations use templates or classes for flexibility.

Example: Using DSU

DSU dsu(n);  // Initialize with n elements
dsu.merge(u, v);  // Union operation
bool connected = dsu.same(u, v);  // Check if in same set
int sz = dsu.size(u);  // Get size of component

Example: Using Dijkstra

Dijkstra<ll> dij(n);  // Initialize with n nodes
dij.addedge(u, v, w);  // Add edge from u to v with weight w
auto dist = dij.run(source);  // Run from source, returns distance vector
auto path = dij.get_path(target);  // Get shortest path to target

Example: Using Bellman-Ford

BellmanFord<ll> bf(n);  // Initialize with n nodes
bf.addedge(u, v, w);  // Add edge from u to v with weight w (can be negative)
auto dist = bf.run(source);  // Run from source, returns distance vector
if (bf.has_negative_cycle()) {
    // Graph contains a negative cycle reachable from source
}
auto path = bf.get_path(target);  // Get shortest path to target

Example: Using Floyd-Warshall

FloydWarshall<ll> fw(n);  // Initialize with n nodes
fw.addedge(u, v, w);  // Add edge from u to v with weight w (can be negative)
bool no_cycle = fw.run();  // Run algorithm, returns true if no negative cycles
if (!fw.has_negative_cycle()) {
    ll dist = fw.get_dist(u, v);  // Get shortest distance from u to v
    auto path = fw.get_path(u, v);  // Get shortest path from u to v
}

Example: Using ModInt

using mint = ModInt<1000000007>;
mint a = 5, b = 3;
mint c = a * b + a / b;  // Automatic modular arithmetic
cout << c << endl;

Example: Using KMP

KMP kmp("pattern");  // Initialize with pattern
auto matches = kmp.find_all("text with pattern");  // Find all occurrences
bool found = kmp.exists("text");  // Check if pattern exists
int count = kmp.count("text");  // Count occurrences

Example: Using Z-algorithm

Zalgo zalgo("pattern");  // Initialize with pattern
auto matches = zalgo.find_all("text with pattern");  // Find all occurrences
bool found = zalgo.exists("text");  // Check if pattern exists
int count = zalgo.count("text");  // Count occurrences
auto z = Zalgo::z_array("string");  // Compute Z-array for any string

Example: Using MST

MST<ll> mst(n);  // Initialize with n nodes
mst.addedge(u, v, w);  // Add edge from u to v with weight w
auto [weight, edges] = mst.run();  // Returns MST weight and edges
ll total_weight = mst.get_weight();  // Get just the weight

Example: Using Topological Sort

TopoSort ts(n);  // Initialize with n nodes
ts.addedge(u, v);  // Add directed edge u -> v
auto order = ts.sort();  // Returns topological order, empty if cycle exists

Example: Using Strongly Connected Components (SCC)

SCC scc(n);  // Initialize with n nodes
scc.addedge(u, v);  // Add directed edge u -> v
auto comps = scc.run();  // Returns list of components (each component is a vector of vertex indices)
int num_comps = scc.comps.size();  // Get number of components
int comp_id = scc.comp[u];  // Get component ID for vertex u
auto comp = scc.comps[scc.comp[u]];  // Get all vertices in same component as u

Example: Using Bridges and Articulation Points

BridgesArt ba(n);  // Initialize with n nodes
ba.addedge(u, v);  // Add undirected edge u-v
ba.run();  // Run the algorithm
// Bridges are stored in ba.bridges (vector of pairs)
// Articulation points are marked in ba.is_art (boolean vector)
bool is_bridge = ba.is_bridge(u, v);  // Check if edge (u,v) is a bridge
bool is_art = ba.is_articulation_point(u);  // Check if vertex u is an articulation point

Coding Style

See STYLE.md for detailed information about the coding conventions used in this library.

PDF Reference Document

You can generate a nicely formatted PDF reference document containing all implementations:

./pdf/generate.sh

This will create contestlib.pdf in the repository root with syntax-highlighted code organized by category. The PDF is useful for quick reference during contests or for printing.

For detailed instructions, prerequisites, and customization options, see pdf/README.md.

Note: The PDF generation logic has been adapted and simplified from Laakeri's contestlib.

Testing

This repository includes a test framework to verify the correctness of implementations.

Running Tests

To run all tests:

make test

To run a specific test (e.g., DSU):

make test-dsu

To clean compiled test binaries:

make clean

Adding New Tests

1. Create a test file in the appropriate subdirectory of tests/ following the naming convention test_*.cpp
2. Include the implementation file using a relative path (e.g., #include "../../datastruct/dsu.cpp")
3. Write test cases using assertions
4. The test will automatically be discovered and compiled by the Makefile

Example test structure:

#include "../../datastruct/dsu.cpp"
#include <cassert>
#include <iostream>

int main() {
    // Test case 1
    DSU dsu(5);
    assert(!dsu.same(0, 1));
    dsu.merge(0, 1);
    assert(dsu.same(0, 1));

    std::cout << "All tests passed!" << std::endl;
    return 0;
}

Contributing

This is a personal competitive programming library. Feel free to use these implementations in your own contests or as reference material.

License

This code is intended for competitive programming use.