Appearance
Common Templates
Copy-paste-ready C++20 templates for contests — I/O, macros, debug, graphs, modular arithmetic, DSU, and segment tree.
Quick Revisit
- Base templates split by test-case mode: single-test and multi-test.
- Reset checklist for global state between test cases.
- Specialized building blocks: ModInt, DSU, iterative segment tree.
- See also: 08-ladder-mixed, Debugging Under Pressure.
Prerequisites: basic C++ fluency, familiarity with STL containers.
Contents
- Base Templates (single-test and multi-test)
- Multi-Test-Case Reset Checklist
- Fast I/O
- Common Macros
- Debug Macro
- Graph Template
- Modular Arithmetic Template
- DSU Template
- Segment Tree Template
- Compilation Flags
- What the Code Won't Teach You
- Self-Test
Base Templates
Two starting points. Pick the one that matches the problem's test-case format — silently leaving cin >> t in a single-test problem (or removing it from a multi-test problem) is one of the most common WA causes on the first submission.
The shared header (types, macros, debug) is identical in both; only main() differs.
Shared header
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vll = vector<vl>;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: ", _dbg(__VA_ARGS__)
#else
#define dbg(...)
#endif
void _dbg() { cerr << "\n"; }
template <typename T, typename... Args>
void _dbg(T x, Args... args) {
cerr << x;
if constexpr (sizeof...(args)) cerr << ", ";
_dbg(args...);
}
void solve() {
// your code here
}Variant A — Single test case
Use when the problem reads input directly without a leading t.
cpp
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}Variant B — Multiple test cases
Use when the input begins with the number of test cases. Declare per-case state inside solve() so it resets automatically; for true globals, use the reset checklist below.
cpp
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) solve();
return 0;
}Multi-Test-Case Reset Checklist
When a problem has T test cases in one run, ALL global state must be reset between cases. Forgetting this causes WA on test 2+ (but passes test 1).
cpp
void solve() {
// ... your solution ...
}
int main() {
int t; cin >> t;
while (t--) {
// Reset everything HERE or inside solve()
solve();
}
}What to reset:
- [ ] Adjacency list:
adj[i].clear()for all i (orfill(adj, adj+n+1, vector<int>())) - [ ] Visited/distance arrays:
fill(vis, vis+n+1, false) - [ ] DSU parent array: re-initialize
par[i] = i - [ ] Global counters (timer for DFS, edge count, etc.)
- [ ] Any
vectorthat getspush_back'd into
MAXN check: Ensure MAXN in your template matches the problem's constraints. Array out of bounds from a too-small MAXN causes RE or silent corruption.
Fast I/O
sync_with_stdio + cin.tie
This is the default for nearly every problem. Two lines at the top of main:
cpp
ios::sync_with_stdio(false);
cin.tie(nullptr);sync_with_stdio(false) decouples C++ streams from C stdio. cin.tie(nullptr) stops cout from flushing before every cin read. Together they make cin/cout competitive with scanf/printf.
Rules after calling these:
- Do NOT mix
cin/coutwithscanf/printfin the same program. - Do NOT use
endl. Use"\n"instead --endlforces a flush.
scanf / printf
Use when I/O volume is extreme (>
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
scanf("%d", &n);
vector<int> a(n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
long long sum = 0;
for (int x : a) sum += x;
printf("%lld\n", sum);
return 0;
}Format specifiers: %d (int), %lld (long long), %f (float), %lf (double), %s (C-string).
Custom fast reader
For the most extreme cases (scanf/printf.
cpp
#include <bits/stdc++.h>
using namespace std;
namespace fast_io {
static const int BUF = 1 << 22;
char buf[BUF], *p = buf, *pe = buf;
inline char gc() {
if (p == pe) pe = buf + fread(buf, 1, BUF, stdin), p = buf;
return *p++;
}
inline int readint() {
int x = 0, neg = 0;
char c = gc();
while (c < '0' || c > '9') { neg = (c == '-'); c = gc(); }
while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
return neg ? -x : x;
}
} // namespace fast_io
int main() {
int n = fast_io::readint();
long long sum = 0;
for (int i = 0; i < n; i++) sum += fast_io::readint();
printf("%lld\n", sum);
return 0;
}Common Macros
Keep a small, stable set. Adding too many macros is a trap -- they obscure bugs and confuse teammates.
Recommended set
cpp
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define pb push_back
#define eb emplace_back
#define fi first
#define se secondType aliases
cpp
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vll = vector<vl>;Use using over typedef -- it reads left-to-right and works with templates.
Loop macros (optional)
Some contestants use these. They save keystrokes but hurt readability:
cpp
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = (a); i >= (b); i--)Decide once and be consistent. If you use them, always use them. Mixing styles during a contest wastes mental bandwidth.
Utility functions
cpp
template <typename T>
T chmin(T &a, T b) { return a = min(a, b); }
template <typename T>
T chmax(T &a, T b) { return a = max(a, b); }These return the new value, so you can chain: chmin(ans, chmin(dp[i], dp[j] + w)).
Debug Macro
Printing variables with their names is essential for contest debugging. This macro works with scalars, pairs, and iterable containers.
cpp
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
template <typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
return os << "(" << p.first << ", " << p.second << ")";
}
template <typename T,
typename = decltype(begin(declval<T>())),
typename = enable_if_t<!is_same_v<T, string>>>
ostream& operator<<(ostream& os, const T& c) {
os << "{";
bool first = true;
for (auto& x : c) {
if (!first) os << ", ";
os << x;
first = false;
}
return os << "}";
}
void _print() { cerr << "\n"; }
template <typename T, typename... Args>
void _print(T x, Args... args) {
cerr << x;
if constexpr (sizeof...(args)) cerr << ", ";
_print(args...);
}
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "] = ", _print(__VA_ARGS__)
#else
#define dbg(...)
#endif
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int x = 42;
vector<int> v = {1, 2, 3};
pair<int, int> p = {10, 20};
map<string, int> m = {{"a", 1}, {"b", 2}};
dbg(x); // [x] = 42
dbg(v); // [v] = {1, 2, 3}
dbg(p); // [p] = (10, 20)
dbg(m); // [m] = {(a, 1), (b, 2)}
dbg(x, v, p); // [x, v, p] = 42, {1, 2, 3}, (10, 20)
return 0;
}Compile with -DLOCAL during testing. On the judge, dbg(...) expands to nothing -- zero overhead.
Graph Template
Unweighted adjacency list
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u); // remove for directed
}
// BFS from node 1
vector<int> dist(n + 1, -1);
queue<int> q;
dist[1] = 0;
q.push(1);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
return 0;
}Weighted adjacency list
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge {
int to;
ll w;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<Edge>> adj(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
ll w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w}); // remove for directed
}
// Dijkstra from node 1
const ll INF = 1e18;
vector<ll> dist(n + 1, INF);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
dist[1] = 0;
pq.push({0, 1});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
return 0;
}Note on indexing: These templates use 1-based indexing (n + 1 sized vectors). Most CF problems use 1-based nodes. If a problem is 0-based, allocate n and adjust.
Modular Arithmetic Template
A ModInt struct that handles modular addition, subtraction, multiplication, and modular inverse automatically. Never worry about forgetting % MOD again.
cpp
#include <bits/stdc++.h>
using namespace std;
template <int MOD>
struct ModInt {
int v;
ModInt() : v(0) {}
ModInt(long long x) : v((x % MOD + MOD) % MOD) {}
friend ModInt operator+(ModInt a, ModInt b) { return ModInt(a.v + b.v); }
friend ModInt operator-(ModInt a, ModInt b) { return ModInt(a.v - b.v + MOD); }
friend ModInt operator*(ModInt a, ModInt b) { return ModInt(1LL * a.v * b.v); }
friend ModInt operator/(ModInt a, ModInt b) { return a * b.inv(); }
ModInt& operator+=(ModInt o) { return *this = *this + o; }
ModInt& operator-=(ModInt o) { return *this = *this - o; }
ModInt& operator*=(ModInt o) { return *this = *this * o; }
ModInt& operator/=(ModInt o) { return *this = *this / o; }
ModInt power(long long e) const {
ModInt res(1), base(v);
for (; e > 0; e >>= 1) {
if (e & 1) res *= base;
base *= base;
}
return res;
}
ModInt inv() const { return power(MOD - 2); }
friend bool operator==(ModInt a, ModInt b) { return a.v == b.v; }
friend bool operator!=(ModInt a, ModInt b) { return a.v != b.v; }
friend ostream& operator<<(ostream& os, ModInt m) { return os << m.v; }
friend istream& operator>>(istream& is, ModInt& m) {
long long x;
is >> x;
m = ModInt(x);
return is;
}
};
using mint = ModInt<998244353>;
// using mint = ModInt<1000000007>;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
mint a = 5, b = 3;
cout << a + b << "\n"; // 8
cout << a - b << "\n"; // 2
cout << a * b << "\n"; // 15
cout << a / b << "\n"; // 5 * inverse(3) mod 998244353
cout << a.power(100) << "\n";
// combinatorics example
int n = 1000;
vector<mint> fact(n + 1), inv_fact(n + 1);
fact[0] = 1;
for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
inv_fact[n] = fact[n].inv();
for (int i = n - 1; i >= 0; i--) inv_fact[i] = inv_fact[i + 1] * (i + 1);
auto C = [&](int n, int k) -> mint {
if (k < 0 || k > n) return 0;
return fact[n] * inv_fact[k] * inv_fact[n - k];
};
cout << C(10, 3) << "\n"; // 120
return 0;
}inv() uses Fermat's little theorem: 998244353 and 10^9 + 7, this is always the case.
Swap the using mint line to change the modulus. The two most common values on CF:
998244353-- NTT-friendly prime, used in polynomial problems.1000000007-- the classic.
DSU Template
Disjoint Set Union (Union-Find) with union by size and path compression. Amortized
cpp
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> p, sz;
int components;
DSU(int n) : p(n), sz(n, 1), components(n) {
iota(p.begin(), p.end(), 0);
}
int find(int x) {
while (x != p[x]) x = p[x] = p[p[x]];
return x;
}
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];
components--;
return true;
}
bool connected(int a, int b) { return find(a) == find(b); }
int size(int a) { return sz[find(a)]; }
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
DSU dsu(n + 1); // 1-based indexing
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
dsu.unite(u, v);
}
cout << dsu.components - 1 << "\n"; // subtract 1 for unused node 0
return 0;
}find uses iterative path splitting (two-pass path compression). unite returns true if the two elements were in different sets, false if already connected -- useful for MST (Kruskal) and cycle detection.
Segment Tree Template
Point update, range query. Parametric on the combine operation.
cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T, T (*combine)(T, T), T (*identity)()>
struct SegTree {
int n;
vector<T> tree;
SegTree() : n(0) {}
SegTree(int n) : n(n), tree(2 * n, identity()) {}
SegTree(const vector<T>& a) : n(a.size()), tree(2 * a.size()) {
for (int i = 0; i < n; i++) tree[n + i] = a[i];
for (int i = n - 1; i > 0; i--) tree[i] = combine(tree[2 * i], tree[2 * i + 1]);
}
void update(int pos, T val) {
pos += n;
tree[pos] = val;
for (pos >>= 1; pos > 0; pos >>= 1)
tree[pos] = combine(tree[2 * pos], tree[2 * pos + 1]);
}
// query on [l, r)
T query(int l, int r) const {
T left_res = identity(), right_res = identity();
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) left_res = combine(left_res, tree[l++]);
if (r & 1) right_res = combine(tree[--r], right_res);
}
return combine(left_res, right_res);
}
T get(int pos) const { return tree[n + pos]; }
};
// --- Configure for your problem ---
// Example 1: Range sum
int sum_combine(int a, int b) { return a + b; }
int sum_identity() { return 0; }
using SumTree = SegTree<int, sum_combine, sum_identity>;
// Example 2: Range min
int min_combine(int a, int b) { return min(a, b); }
int min_identity() { return INT_MAX; }
using MinTree = SegTree<int, min_combine, min_identity>;
// Example 3: Range max
int max_combine(int a, int b) { return max(a, b); }
int max_identity() { return INT_MIN; }
using MaxTree = SegTree<int, max_combine, max_identity>;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int& x : a) cin >> x;
SumTree seg(a);
while (q--) {
int type;
cin >> type;
if (type == 1) {
int pos, val;
cin >> pos >> val;
seg.update(pos, val); // 0-indexed
} else {
int l, r;
cin >> l >> r;
cout << seg.query(l, r) << "\n"; // [l, r)
}
}
return 0;
}Key details:
- This is a bottom-up (iterative) segment tree. It uses
memory and is faster than recursive implementations due to fewer function calls. - Indexing is 0-based.
query(l, r)covers the half-open interval. - To adapt for a new operation: define a
combinefunction and anidentityfunction (the identity element for the operation), then create a type alias. - For range update + range query, you need lazy propagation -- see Segment Tree with Lazy Propagation.
Compilation Flags
Standard contest compilation
g++ -std=c++20 -O2 -Wall -Wextra -DLOCAL -o sol sol.cpp| Flag | Purpose |
|---|---|
-std=c++20 | Enable C++20 features (structured bindings, ranges, concepts) |
-O2 | Optimization level matching most judges |
-Wall -Wextra | Catch common mistakes at compile time |
-DLOCAL | Define LOCAL macro so dbg(...) prints output |
Debugging build
g++ -std=c++20 -O0 -g -Wall -Wextra -Wshadow -DLOCAL \
-fsanitize=address,undefined \
-fno-omit-frame-pointer \
-o sol sol.cpp| Flag | Purpose |
|---|---|
-O0 -g | No optimization + debug symbols for readable stack traces |
-fsanitize=address | Detects out-of-bounds access, use-after-free, memory leaks |
-fsanitize=undefined | Detects signed overflow, null dereference, shift errors |
-Wshadow | Warns when a local variable shadows an outer one |
-fno-omit-frame-pointer | Ensures complete stack traces in sanitizer output |
Use the debugging build when testing locally. The sanitizers catch bugs that would otherwise produce wrong answers or runtime errors on the judge. Switch to the standard build only for performance testing.
Makefile snippet
makefile
CXX = g++
CXXFLAGS = -std=c++20 -Wall -Wextra -Wshadow -DLOCAL
debug: CXXFLAGS += -O0 -g -fsanitize=address,undefined -fno-omit-frame-pointer
debug: sol
release: CXXFLAGS += -O2
release: sol
sol: sol.cpp
$(CXX) $(CXXFLAGS) -o $@ $<
clean:
rm -f sol
.PHONY: debug release cleanUsage: make debug for local testing, make release for performance checks.
What the Code Won't Teach You
Insights drawn from reflection notes
Template adaptation is the skill, not template selection. The value of a template is knowing how to modify it quickly and correctly under pressure. A correct adaptation of a simple template beats a wrong adaptation of a sophisticated one every time.
Every line exists for a reason. ios::sync_with_stdio(false) decouples C++ streams. cin.tie(nullptr) stops cout flushing before cin reads. using ll = long long prevents overflow. If you can't explain why a line is in your template, it's a liability -- you'll break its invariant during adaptation.
"Contest-ready" has a definition. A template is contest-ready when: (1) you've debugged it on at least 3 real problems, (2) you can explain every line, (3) you know what to change for common variants.
TEMPLATE MATURITY SPECTRUM:
┌──────────────┬─────────────────┬──────────────────┐
│ Beginner │ Intermediate │ Expert │
├──────────────┼─────────────────┼──────────────────┤
│ 500-line │ 30-line base + │ 20-line base, │
│ mega-template│ separate ref │ everything typed │
│ with BIT, │ files per algo │ from memory in │
│ segtree, DSU │ │ < 2 minutes │
│ all pasted │ Pull only what │ │
│ │ you need │ Adaptations are │
│ Can't debug │ │ instant and │
│ when it │ Understood and │ correct │
│ breaks │ tested │ │
└──────────────┴─────────────────┴──────────────────┘Mental Traps
Integrated from reflection notes
Trap: "The faster I paste, the better."
Paste speed is not the bottleneck. Correctness of the pasted code is. A 30-second paste that produces a wrong adaptation costs more time (debugging + penalty) than a 2-minute careful paste.
Trap: "More lines = more powerful template."
Templates should be minimal. A 300-line "might be useful" template is harder to debug than a clean 30-line skeleton. Keep specialized code in separate reference files, not in the base template.
Trap: "I'll remember what the template does when I need to modify it."
Under contest pressure, memory for "why does this line exist" degrades significantly. Write clear variable names. Not because it's good style -- because future-contest-you will need them at 1am when staring at a subtle bug.
Trap: "My globals will be fine across test cases."
Codeforces Round 847, problem B. Multi-test format, set. Submit. WA on test 2. Fifteen minutes of debugging reveals the logic is bulletproof. The issue: set declared globally, never cleared between cases -- the answer for case 3 still contains elements from case 2. A single s.clear() at the top of the loop fixes it. Penalty: +15 minutes and one wrong submission. In multi-test problems, the first line of your solve function should clear every data structure. Build this into your template as a comment: // RESET HERE. Better yet, declare data structures inside the solve function so they auto-reset.
TEMPLATE CHECKLIST BEFORE CONTEST:
┌─ File ready? ──────────────────────────────┐
│ □ Template pasted in editor │
│ □ Compilation command in terminal history │
│ □ Debug flags (-DLOCAL -fsanitize) ready │
│ □ Stress test files (gen/brute/run.sh) in │
│ working directory │
└─────────────────────────────────────────────┘
┌─ Common adaptations rehearsed? ────────────┐
│ □ Single test case (comment out cin >> t) │
│ □ Graph input (adj list from edges) │
│ □ Modular arithmetic (which MOD?) │
│ □ Multi-test reset (clear globals) │
└─────────────────────────────────────────────┘Self-Test
Drawn from reflection notes
[ ] Type your contest template from memory -- no looking. Time it. Target: under 2 minutes. If slower, practice daily until automatic.
[ ] Modify the template for a multi-test-case problem using a BIT of size
. What needs to reset between test cases? Write the exact reset code. [ ] Identify every line in your template and state in one phrase what it does and why. Any line you can't explain is a liability -- fix that understanding now.
[ ] Recall one problem where you got WA from a template mistake (wrong MAXN, missing reset, wrong global). If this hasn't happened yet, it will -- building awareness now saves future time.
[ ] Keep your base template under 40 lines. Count yours. If longer, identify what to cut. Specialized code (segtree, DSU) belongs in separate reference files.