i. C++ for Competitive Programming

The language-level facts that decide WA/TLE/RE before any algorithm does. Everything here is GCC on a 64-bit Linux judge (Codeforces, AtCoder, ICPC), C++20 unless noted.

The template

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
#define all(x) (x).begin(), (x).end()
#define sz(x) int((x).size())
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
void solve() {
}
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t = 1;
    cin >> t;
    while (t--) solve();
}

• ckmin(d[v], d[u] + w) both relaxes and reports whether it changed, which is exactly what Dijkstra, Bellman-Ford and DP relaxations want.
• Seed randomness with time. Fixed seeds make hashing and random pivots hackable.
• Remove cin.tie(nullptr) only if you rely on auto-flush; for interactive problems flush explicitly instead (see Interactive Problems).
• The full library lives in Templates; this page is about the language.

Integer types and overflow

Type	Max	Use
int	$2.1\cdot 10^9$	indices, counts
unsigned	$4.3\cdot 10^9$	hashing mod $2^{32}$
long long	$9.2\cdot 10^{18}$	sums, products of two ints
unsigned long long	$1.8\cdot 10^{19}$	hashing mod $2^{64}$, bitsets of 64
__int128	$1.7\cdot 10^{38}$	$a\cdot b\mathrm{mod}m$ for $m\sim 10^{18}$, exact geometry with $10^9$ coordinates cubed

The overflow rule

The type of a * b is decided by the operands, not by the variable you assign to. ll x = a * b; with int a, b overflows. Write 1LL * a * b.

Overflow checklist:

• Sum of $n=2\cdot 10^5$ values of size $10^9$ needs ll. accumulate(all(v), 0) sums in int; write 0LL.
• 1 << 40 is UB; write 1LL << 40. Shifting by $\ge$ width is UB even for unsigned.
• INF = 1e18 plus anything overflows. Use INF = 4e18 only if you never add to it, otherwise LLONG_MAX / 4, and guard if (d[u] == INF) continue;.
• abs(INT_MIN) and -LLONG_MIN overflow.
• Signed overflow is UB, and the optimizer exploits it (loops whose bound check silently disappears). Unsigned wraps mod $2^k$ and is well defined.
• Overflow-checked multiply: __builtin_mul_overflow(a, b, &res) returns true on overflow. Also __builtin_add_overflow.

__int128 has no stream I/O:

string to_str(i128 x) {
    if (x == 0) return "0";
    bool neg = x < 0; if (neg) x = -x;
    string s;
    while (x) s += char('0' + x % 10), x /= 10;
    if (neg) s += '-';
    return {s.rbegin(), s.rend()};
}

Division, modulo and rounding

C++ truncates toward zero: -7 / 2 == -3, -7 % 2 == -1. Mathematical versions:

ll floordiv(ll a, ll b) { return a / b - ((a % b != 0) && ((a < 0) != (b < 0))); }
ll ceildiv(ll a, ll b)  { return a / b + ((a % b != 0) && ((a < 0) == (b < 0))); }
ll md(ll a, ll m)       { a %= m; return a < 0 ? a + m : a; }

• (a + b - 1) / b is ceil only for $a\ge 0,b>0$.
• Integer square root: ll r = sqrtl(n); while (r * r > n) r--; while ((r + 1) * (r + 1) <= n) r++;. Never trust sqrt alone near $10^{18}$.
• Integer log: __lg(x) is $\lfloor {\log }_{2}x\rfloor$ for $x>0$; C++20 bit_width(x) - 1 is the same.
• pow returns double. Never use it for integers.

size() is unsigned

v.size() - 1 on an empty vector is $2^{64}-1$, so for (int i = 0; i < v.size() - 1; i++) runs forever. Cast with sz(v). Same trap with s.size() - k in string loops.

Containers

Container	Access	Insert / erase	Notes
vector	$O(1)$	$O(1)$ amortized at back	contiguous, by far the fastest
deque	$O(1)$	$O(1)$ at both ends	chunked, around 2x slower than vector, high memory per instance
set, map, multiset	—	$O(\log n)$	red-black tree, ordered, predecessor/successor
unordered_map	$O(1)$ avg	$O(1)$ avg	hackable, large constant, use a custom hash
priority_queue	top $O(1)$	$O(\log n)$	max-heap by default
bitset<N>	$O(1)$	—	word-parallel ops in $O(N/64)$
PBDS tree	—	$O(\log n)$	adds order_of_key, find_by_order (PBDS)

The six classic traps:

1. std::lower_bound(all(s), x) on a set is $O(n)$ (no random access). Use s.lower_bound(x).
2. ms.erase(x) on a multiset erases every copy. Use ms.erase(ms.find(x)).
3. unique only moves adjacent duplicates to the back. Sort first, then v.erase(unique(all(v)), v.end()).
4. Iterator invalidation: vector on reallocation (including push_back while iterating), deque on any insertion, set/map only for the erased node. auto& x = v[0]; v.push_back(..) leaves x dangling.
5. map[k] inserts k if absent. Use count/find/contains (C++20) in read-only checks, or the map grows.
6. vector<bool> is bit-packed with proxy references. Use vector<char> for a real boolean array, bitset for bit tricks.

Min-heap: priority_queue<T, vector<T>, greater<T>>. There is no decrease-key; push the new value and skip stale entries on pop (lazy deletion).

Hashing safely

The default hash<long long> is the identity, so anti-hash tests force $O(n)$ per operation. Use splitmix64 with a runtime seed:

struct SafeHash {
    static ull splitmix64(ull x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
    size_t operator()(ull x) const {
        static const ull SEED = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + SEED);
    }
};
unordered_map<ll, int, SafeHash> mp;
mp.reserve(1 << 20); mp.max_load_factor(0.25);   // often 2x faster

For pairs, hash x * 1'000'000'007 + y or combine two splitmix values. __gnu_pbds::gp_hash_table<ll, int, SafeHash> is usually 2-3x faster than unordered_map. Often the fastest of all is to avoid hashing: sort plus binary search, or coordinate compression into an array.

Algorithms worth knowing by heart

sort(all(a)); stable_sort(all(a));                   // introsort; stable = merge sort
nth_element(a.begin(), a.begin() + k, a.end());       // k-th smallest in O(n) average
partial_sort(a.begin(), a.begin() + k, a.end());      // smallest k sorted, O(n log k)
lower_bound / upper_bound / equal_range               // first >= x, first > x, both
a.erase(unique(all(a)), a.end());                     // dedupe a sorted range
next_permutation(all(a));                             // start from sorted to get all n!
iota(all(p), 0);                                      // 0, 1, 2, ...
partial_sum(all(a), pre.begin() + 1);                 // prefix sums
rotate(a.begin(), a.begin() + k, a.end());            // left rotate by k
merge(all(a), all(b), back_inserter(c));              // merge two sorted ranges
inplace_merge(first, mid, last);                      // merge sort step
max_element / min_element / minmax_element           // return iterators
count_if / all_of / any_of / none_of / find_if
gcd(a, b); lcm(a, b);                                 // <numeric>, C++17
midpoint(a, b);                                       // no overflow, C++20

C++20 <bit>: popcount, countl_zero, countr_zero, bit_width, bit_floor, bit_ceil, has_single_bit (unsigned arguments only). See Bit Tricks.

C++20 ranges shorten common code: ranges::sort(a), ranges::lower_bound(a, x), ranges::max(a), for (int i : views::iota(0, n)), for (auto x : a | views::reverse).

Comparators

A comparator must be a strict weak ordering: cmp(a, a) is false, and incomparability is transitive. A comparator with <= is undefined behaviour and does crash std::sort (it walks off the array) on large inputs.

sort(all(v), [](const auto& a, const auto& b) {
    if (a.first != b.first) return a.first < b.first;
    return a.second > b.second;          // tie-break descending
});
sort(all(v), [](auto& a, auto& b) { return tie(a.x, b.y) < tie(b.x, a.y); }); // lexicographic via tuples

• For an exchange-argument sort (a before b iff $f(a,b)<f(b,a)$), verify transitivity. Sorting fractions $a/b$ must compare a1 * b2 < a2 * b1 in ll/i128, never as double.
• Floating comparators with an epsilon are not strict weak orderings. Never put them in a set.
• For a custom set order with equal keys, the set treats !cmp(a,b) && !cmp(b,a) as equal and drops duplicates. Add an id as a tie-breaker.

References, copies, lambdas

for (auto& [k, v] : mp) v *= 2;           // modifies
for (const auto& s : strs) use(s);        // no copy
for (auto s : strs) use(s);               // copies every string: silent TLE

Pass containers by reference. A recursive function taking vector<int> g by value copies it on every call.

Recursive lambdas:

auto dfs = [&](auto&& self, int v, int p) -> void {
    for (int u : g[v]) if (u != p) self(self, u, v);
};
dfs(dfs, 0, -1);
// C++23: auto dfs = [&](this auto&& self, int v, int p) -> void { ... }; dfs(0, -1);

function<void(int,int)> also works, but it is slower (type-erased call) and cannot be inlined.

Recursion depth

Each frame costs roughly 50-200 bytes. A DFS on a path of $10^6$ vertices needs 100+ MB of stack.

• Codeforces and most judges give a large stack, but Windows judges default to 1 MB (Codeforces sets 256 MB).
• Options: iterative DFS with an explicit stack, BFS order processed in reverse (works for most tree DPs), or run the solution on a thread with a big stack.
• Locally: ulimit -s unlimited, or with MinGW -Wl,--stack,268435456.

// tree DP without recursion: BFS order, then process in reverse
vector<int> order = {0}, par(n, -1);
for (int i = 0; i < sz(order); i++) {
    int v = order[i];
    for (int u : g[v]) if (u != par[v]) par[u] = v, order.push_back(u);
}
for (int i = n - 1; i > 0; i--) { int v = order[i]; /* combine v into par[v] */ }

Recursion shapes worth recognising, beyond depth: linear ($f(n)\to f(n-1)$, e.g. factorial), binary split ($f(l,r)\to f(l,m),f(m,r)$, e.g. merge sort, segment trees), choice/enumeration (include-or-skip each element, e.g. subset backtracking), tree traversal (recurse on children), mutual recursion ($f$ calls $g$ calls $f$, e.g. expression parsing). Every recursive solution needs a base case, a reduction to strictly smaller instances, and a combine step; a missing or unreachable base case is a silent infinite recursion (RE, not WA), and exponential blow-up from repeated subproblems is the signal to memoize (Memoization).

Undefined behaviour that “works locally”

Code	Problem
a[i++] = i	unsequenced modification
reading an uninitialized local	random value; globals are zeroed, locals are not
v[v.size()], s[-1]	out of bounds; sometimes silent
missing return in non-void function	UB, frequently a crash with -O2
comparator with <=	sort reads out of range
int overflow inside a loop condition	loop may never terminate
large local arrays	stack overflow. Make big arrays global or static
unparenthesized macros	#define SQ(a) a*a expands SQ(3+3) to 3+3*3+3=15, not 36 — always write #define SQ(a) ((a)*(a))

Compile locally with -D_GLIBCXX_DEBUG -fsanitize=address,undefined -g to turn most of these into immediate errors (Debugging).

Floating point

• Never compare with ==. Prefer exact integer arithmetic: compare $a/b<c/d$ as $ad<cb$, distances squared, cross products in ll.
• long double is 80-bit on x86 GCC (about 18-19 significant digits) and is usually worth it in geometry. Print with cout << fixed << setprecision(10).
• acosl(-1.0L) gives $\pi$ at full precision.
• Details: Floating Point.

Precompute once, query many

With $T$ test cases and a global bound, build tables outside the test loop: factorials and inverse factorials, smallest prime factor, powers of the hash base, $\phi /\mu$, popcount tables. Recomputing per test is a classic TLE with $T=10^5$.

Do not memset or assign an array of size $10^6$ per test case when the test is tiny: the sum of $n$ is bounded, the sum of MAXN is not. Clear only what you used.

Hard-coding: if the input is a single small parameter and the answer is slow to compute, precompute answers locally (every $10^6$-th value, or all of them if few), paste them into the source (judges allow about 64 KB of code) and finish from the nearest checkpoint.

Constants

const int MOD = 998244353;        // = 119 * 2^23 + 1, NTT-friendly; 1e9 + 7 otherwise
const ll INF = LLONG_MAX / 4;     // room to add a few without overflow
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
const long double PI = acosl(-1.0L);

int INF = 1e9 lets INF + INF fit in ll but not in int. Pick the sentinel so the arithmetic you do on it cannot overflow, and still guard unreachable states.

A byte count in MiB divides by $2^{20}$; a decimal MB divides by $10^6$ — judges state memory limits in MiB-sized powers of two but sometimes label them “MB,” so check which is meant before trusting a tight estimate.

Utilities

Calendar (proleptic Gregorian, day 1 = 0001-01-01, 0 = Monday):

bool isLeap(ll y) { return y % 4 == 0 && (y % 100 != 0 || y % 400 == 0); }
int daysIn(ll y, int m) { static int d[] = {31,28,31,30,31,30,31,31,30,31,30,31}; return m == 2 && isLeap(y) ? 29 : d[m - 1]; }
ll daysBefore(ll y) { y--; return y * 365 + y / 4 - y / 100 + y / 400; }
ll ordinal(ll y, int m, int d) { ll r = daysBefore(y) + d; for (int i = 1; i < m; i++) r += daysIn(y, i); return r; }
int dayOfWeek(ll y, int m, int d) { return (ordinal(y, m, d) - 1) % 7; }

The Gregorian calendar repeats every 400 years (146097 days, a multiple of 7), which is how “count Fridays the 13th in $[1,10^{18}]$” is done.

Proof: the 400-year cycle has 146097 days, a multiple of 7

In any 400 consecutive years, the leap-year rule (divisible by 4, except centuries, except multiples of 400) gives $400/4-400/100+400/400=100-4+1=97$ leap years, so the cycle has $400\cdot 365+97=146097$ days. Dividing: $146097=7\cdot 20871$ exactly, so the day-of-week pattern (and hence the full calendar, since the leap-year rule itself has period exactly 400 years) repeats identically every 400 years — a date $400k$ years later falls on the same day of the week. Tested: ordinal/dayOfWeek above were checked against Python’s datetime.date.toordinal()/.weekday() for every day of years 1 and 4, and spot-checked every 7th day of years 100, 400, 401, 1600, 1700, 1752, 1900, 2000, 2024, 2400 (centuries and the 400-multiple boundaries where the rule actually branches) — all matched. $■$

Random helpers:

ll rnd(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
shuffle(all(v), rng);

Never use rand(): on Windows judges RAND_MAX is 32767.