---
title: "Contest Template"
summary: One file of includes, typedefs and helpers that covers every algorithm in this book — with the settings you should not change.
difficulty: core
tags: [template, reference]
prereq: [foundations/intro]
see: [appendix/notation, special/independent]
---

:::note title="How to use this page"
Copy it into your editor's snippet, then *delete* what you do not need. A template that grows past ~200 lines stops being a template: you begin to carry bugs you never read. The sections below are ordered by how often they are used in this book.
:::

## The template

```cpp template.cpp
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int,int>;
const int INF = 0x3f3f3f3f;
const ll LINF = (ll)4e18;

// ---------- modular arithmetic (prime modulus arithmetic, @matrices/recurrences) ----------
struct Mod {
    static const ll P = 998244353;
    static ll powm(ll a, ll e = P - 2) { ll r = 1; for (; e; e >>= 1, a = a * a % P) if (e & 1) r = r * a % P; return r; }
};
inline void add(ll &a, ll b) { a += b; if (a >= Mod::P) a -= Mod::P; }

// ---------- DSU with size, no path compression when rollback is needed (@structures/dsu) ----------
struct DSU {
    vector<int> p, sz;
    DSU(int n = 0) { reset(n); }
    void reset(int n) { p.resize(n); sz.assign(n, 1); iota(p.begin(), p.end(), 0); }
    int find(int v) { return p[v] == v ? v : p[v] = find(p[v]); }
    bool unite(int a, int b) {
        a = find(a); b = find(b); if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b); p[b] = a; sz[a] += sz[b]; return true;
    }
    int size(int v) { return sz[find(v)]; }
};

// ---------- Fenwick over int or ll (1-indexed) (@structures/fenwick) ----------
struct BIT {
    vector<ll> t; int n;
    BIT(int n = 0) : t(n + 1, 0), n(n) {}
    void add(int i, ll v) { for (; i <= n; i += i & -i) t[i] += v; }
    ll sum(int i) { ll r = 0; for (; i > 0; i -= i & -i) r += t[i]; return r; }
    ll range(int l, int r) { return sum(r) - sum(l - 1); }
    int kth(ll k) { int i = 0; for (int b = 31 - __builtin_clz(n); b >= 0; b--) if (i + (1 << b) <= n && t[i + (1 << b)] < k) { i += 1 << b; k -= t[i]; } return i + 1; }
};

// ---------- Segment tree, iterative, any associative op (@structures/segment-tree) ----------
template <class T, T (*F)(T, T)>
struct Seg {
    int n; vector<T> t;
    Seg(const vector<T> &a) : n(a.size()), t(2 * n) {
        copy(a.begin(), a.end(), t.begin() + n);
        for (int i = n - 1; i > 0; i--) t[i] = F(t[2*i], t[2*i+1]);
    }
    void setp(int i, T v) { for (t[i += n] = v; i > 1; i >>= 1) t[i >> 1] = F(t[i], t[i ^ 1]); }
    T query(int l, int r) { T L{}, R{}; for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if (l & 1) L = F(L, t[l++]); if (r & 1) R = F(t[--r], R); } return F(L, R); }
};

// ---------- binary lifting + LCA (@lca/binary-lifting) ----------
// ---------- Dinic (@flow/maxflow) ----------
// ---------- Kuhn / Hopcroft-Karp (@matching/bipartite) ----------
// ... deliberately not repeated here: copy the version from the page you are using.

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tc = 1;
    // cin >> tc;                       // uncomment for multi-test cases
    while (tc--) {
    }
    return 0;
}
```

## Settings that are not style preferences

:::props title="Settings that are not style preferences"
- `#include <bits/stdc++.h>` + `using namespace std`: fine on Codeforces/CSES/AtCoder (GCC); for a judge with a strict compiler, list the ~10 real headers instead,
- **`ios::sync_with_stdio(false); cin.tie(nullptr);`** — without it, `cin` on 10⁶ integers can TLE by itself,
- `INF = 0x3f3f3f3f` (≈ 1.06·10⁹): the only 32-bit-ish "infinity" where `INF + INF` doesn't overflow and `memset(a, 0x3f, sizeof a)` fills it,
- `const ll LINF = 4e18`: use for distances/flows that can sum to 10¹⁸; `LLONG_MAX` breaks `d + w` comparisons silently,
- recursion depth: if your DFS may reach 10⁶ frames, either write it iteratively or start the process with a large stack (Codeforces: `#pragma comment(linker, ...)` on Windows, `ulimit -s unlimited` locally, or an explicit stack everywhere — @foundations/walks' "iteration or nothing" rule),
- **never** `using namespace std;` inside a header you include twice; the template is a single .cpp, which is why it is allowed,
- `int` for indices even when values need `ll`: mixing types in comparisons produces signed/unsigned warnings that hide real bugs.
:::

## Three anti-patterns

:::warning title="Three template anti-patterns"
1. **Un-tested code in the template.** If a routine is not in a recent solved problem, it does not belong there — a bug in the template costs you every problem,
2. **Ten alternatives for the same task** (Kruskal + Prim + Borůvka): keep the one you can write from memory under pressure; the others live in this book,
3. **Macro soup** (`#define rep(i,a,b) for(...)`): saves 60 characters, costs readability when you debug at minute 100. If you use them, keep them to `all(x)`, `sz(x)`, and nothing else.
:::

## Debug block

:::note title="Debug block — delete before submitting, keep while working"
```cpp debug.cpp
#ifndef ONLINE_JUDGE
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#else
#define dbg(...) ((void)0)
#endif
// plus the one-line container printer you always want:
template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
    for (auto &x : v) os << x << ' '; return os;
}
```
`#ifndef ONLINE_JUDGE` is the switch that makes the same file safe to submit; `cerr` is not captured by the judge, so leftover prints there never cost you a WA — only the flush cost, which is why `dbg` uses `fprintf(stderr, ...)` and not `cout`.
:::

## Stress testing

:::props title="Stress testing (the only testing skill that wins contests)"
Three files: `gen.py` (random small instance), `brute.cpp` (a solution you trust: $O(n^2)$, no cleverness), `sol.cpp` (yours), and a loop:
```sh
for i in $(seq 1 2000); do
  python3 gen.py $i > in.txt
  ./brute < in.txt > b.out ; ./sol < in.txt > s.out
  cmp b.out s.out || { echo "MISMATCH on $i"; cp in.txt case.txt; break; }
done
```
`case.txt` is then your minimisation input: shrink it by hand or with a delta-debugging loop. For every graph problem in this book, a brute force exists that is one DFS — the pairing "random graph + naive check" finds the corner case (disconnected, self-loop, parallel edge, n = 1) in under a minute, which is faster than any amount of staring.
:::