whoashish's cp notes

Contest Template

3 min read

The file you start every problem from. Short by design.

The minimal template

#include <bits/stdc++.h>
using namespace std;
 
using ll  = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<class T> using V  = vector<T>;
template<class T> using VV = vector<vector<T>>;
 
#define all(x)  (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x)   ((int)(x).size())
 
void solve() {
    // ---- per test case ----
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;                    // delete this line for single-test problems
    while (t--) solve();
    return 0;
}

That is the whole thing. Everything else is pasted only when needed.

Why each line is there

LineReason
bits/stdc++.hone include; GCC-only, but every judge that matters uses GCC
sync_with_stdio(false)detaches C++ streams from C stdio — often a 3-5x I/O speedup
cin.tie(nullptr)stops cout flushing before every cin; remove for interactive problems
using lloverflow is the single most common WA; ll should be effortless to type
all(x)sort(all(v)) reads better and is harder to typo than the two-iterator form
sz(x).size() is unsigned; sz(v) - 1 on an empty vector is a disaster without the cast

endl flushes

Use '\n'. In a loop printing lines, endl can cost a second on its own.

Common constants

const int  INF  = 1e9 + 7;          // fits in int, and INF + INF still fits in ll
const ll   LINF = 4e18;             // just under LLONG_MAX ~ 9.2e18
const int  MOD  = 1e9 + 7;          // 998244353 for NTT problems
const double EPS = 1e-9;
const double PI  = acos(-1.0);
const int dx[] = {1,-1,0,0}, dy[] = {0,0,1,-1};       // 4-directional grid

Choosing INF = 1e9 rather than INT_MAX means INF + x does not overflow in shortest-path relaxations — a small choice that prevents a real class of bug.

Optional additions

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }

A time-seeded RNG matters: fixed-seed unordered_map hashing and fixed random pivots are both hackable on Codeforces. See Pitfalls.

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, true : false; }

ckmin(dist[v], dist[u] + w) both updates and tells you whether it changed — exactly what relaxation loops want.

Pragmas — use with care

#pragma GCC optimize("O2","unroll-loops")
#pragma GCC target("avx2")            // only if the judge supports it

These can give a genuine 2-4x speedup on tight numeric loops, and can also crash on judges with older CPUs. They are a last resort after the complexity is right, never a substitute for it. See Constant Factor Optimization.

Reading input fast

For very large input ( numbers), a hand-rolled reader beats even unsynced cin:

static char buf[1 << 25];
int readInt() {
    static int pos = 0;
    while (buf[pos] < '0' && buf[pos] != '-') pos++;
    int s = 1; if (buf[pos] == '-') { s = -1; pos++; }
    int x = 0;
    while (buf[pos] >= '0') x = x * 10 + (buf[pos++] - '0');
    return x * s;
}
// fread(buf, 1, sizeof buf, stdin);   in main

Reach for this only when I/O is measurably the bottleneck. See I/O Optimization.

See also: Debug Macros · Stress Testing · C++ Tips

Graph View