In competitive programming environment, such as codeforces, C++ dominates the field.
However, some people might prefer C to C++. Nor's blog explains the reasoning excellently, which I will not repeat here.
This blog will focus on practical way to mitigate not having the Standard Template Library and how those data structures can be replaced with simple C code
Starting off with the most frequently used container in STL. std::vector, or dynamic arrays, are very convenient for tasks such as storing adjacency list.
Notice that in many cases, we do not need to push the elements to vectors in an online manner. So we can replace it with simple (ptr, sz) array. Consider the code below, which construct an adjacency list when given edge list.
#define N 100001
int *adj[N], sz[N];
#define M 200002
int edge_u[M], edge_v[M];
int n, m;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i)
{
scanf("%d%d", &edge_u[i], &edge_v[i]);
++sz[edge_u[i]], ++sz[edge_v[i]];
}
for (int i = 0; i < n; ++i)
{
adj[i] = malloc(sizeof(int) * sz[i]);
sz[i] = 0;
}
for (int i = 0; i < m; ++i)
{
adj[edge_u[i]][sz[edge_u[i]]++] = edge_v[i];
adj[edge_v[i]][sz[edge_v[i]]++] = edge_u[i];
}
return 0;
}
Of course, this require two pass of the edge list. In a more complicated situation, a two-pass is not really favorable. So what if you need an online vector?
Turns out, dynamic array is easy to implemnt! Thanks to rainboy for this code
#include <stdlib.h>
int *ej[N], eo[N];
void append(int i, int j)
{
int o = eo[i]++;
if (! o)
ej[i] = (int *) malloc(sizeof **ej * 2);
else if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
This is the easiest to recreate, all you need for a linked-list is two arrays.
Consider this code for storing adjacency list as linked list.
#define N 100005
#define M 200001
int nxt[M * 2], to[M * 2], head[N], ii;
void add_edge(int u, int v)
{
int j = ++ii;
nxt[j] = head[u];
to[j] = v;
head[u] = j;
}
Let's focus on a large subset of usecases where the key of set(or map) are integers.
You can replace the functionalities with segment tree! (sparse, if necessary)
How?To insert (key, val) into the map, set position `key` of the segment tree to `val`.
To find maximum, minimum, next greater(less), previous greater(less) key in the map, just binary search on the segment tree (or "walk on segtree").
Refer to my submission to the problem 609F which utilize sprase segment tree to support these operations.
#include <stdio.h>
#define assert_(x) if (!(x)) __builtin_trap()
#define N ( 1 << 18 )
#define M 30000000
int n, m
, x[N], f, f0, ate[N]
, A[M], Lz[M], L[M], R[M], ii, rt, xi
, waitlist, list[N], link[N], jj;
long long t[N];
int new_()
{
int p;
p = ++ii;
L[p] = R[p] = 0;
A[p] = f0;
Lz[p] = -1;
return p;
}
void pus(int v, int l, int r)
{
if (0 == v || -1 == Lz[v])
return;
A[v] = Lz[v];
if (l < r)
{
if (!L[v]) L[v] = new_();
if (!R[v]) R[v] = new_();
Lz[L[v]] = Lz[v];
Lz[R[v]] = Lz[v];
}
Lz[v] = -1;
}
int point(int v, int l, int r, int p)
{
pus(v, l, r);
if (!v)
return f0;
if (l == r)
return A[v];
if (p <= (l + r) / 2)
return point(L[v], l, (l + r) / 2, p);
return point(R[v], (l + r) / 2 + 1, r, p);
}
void update(int *v, int l, int r, int x, int y, int k)
{
pus(*v, l, r);
if (!*v)
*v = new_();
if (r < x || y < l)
return;
if (x <= l && r <= y)
{
Lz[*v] = k;
pus(*v, l, r);
return;
}
update(&L[*v], l, (l + r) / 2, x, y, k);
update(&R[*v], (l + r) / 2 + 1, r, x, y, k);
A[*v] = A[L[*v]] > A[R[*v]] ? A[L[*v]] : A[R[*v]];
}
int search_(int *v, int l, int r, int k)
{
int res;
if (!*v)
*v = new_();
pus(*v, l, r);
if (A[*v] < k)
return -1;
if (l == r)
return l;
res = search_(&L[*v], l, (l + r) / 2, k);
if (-1 != res)
return res;
return search_(&R[*v], (l + r) / 2 + 1, r, k);
}
int search(int *v, int l, int r, int x, int y, int k)
{
int res;
if (!*v)
*v = new_();
pus(*v, l, r);
if (A[*v] < k || r < x || y < l)
return -1;
if (x <= l && r <= y)
return search_(v, l, r, k);
res = search(&L[*v], l, (l + r) / 2, x, y, k);
if (-1 != res)
return res;
return search(&R[*v], (l + r) / 2 + 1, r, x, y, k);
}
int end(int i)
{
if (x[i] + t[i] > f)
return f;
return (int)(x[i] + t[i]);
}
void eat(int i, int inc)
{
t[i] += inc;
++ate[i];
}
void stretch_tongue(int i)
{
int j0, j, changes;
changes = 0;
j = search(&waitlist, 0, f, x[i], end(i), f0 + 1);
j0 = j;
if (-1 == j)
return;
j = point(waitlist, 0, f, j);
j -= f0;
for (; j; j = link[j])
{
eat(i, list[j]);
++changes;
}
update(&waitlist, 0, f, j0, j0, f0);
if (!changes)
return;
stretch_tongue(i);
}
void own(int i)
{
int st;
st = search(&rt, 0, f, x[i], end(i), x[i]);
if (-1 == st)
return;
update(&rt, 0, f, st, end(i), x[i]);
}
int main()
{
int i;
f0 = 1e9 + 1;
f = 1e9 + 555;
scanf("%d%d", &n, &m);
for (i = 0; i < n; ++i)
{
scanf("%d%lld", x + i, t + i);
update(&xi, 0, f, x[i], x[i], i);
own(i);
}
for (i = 0; i < m; ++i)
{
int j, p, b;
scanf("%d%d", &p, &b);
j = point(rt, 0, f, p);
if (j == f0)
{
int j_, prev;
prev = point(waitlist, 0, f, p);
j_ = ++jj;
link[j_] = prev - (int)f0;
list[j_] = b;
update(&waitlist, 0, f, p, p, j_ + (int)f0);
}
else
{
j = point(xi, 0, f, j);
eat(j, b);
stretch_tongue(j);
own(j);
}
}
for (i = 0; i < n; ++i)
printf("%d %lld\n", ate[i], t[i]);
return 0;
}
In rare cases where you need set(or map) where the keys are not integer, writing a Treap is relatively easy.
priority queue / dijkstra's algorithm
Of course, priority queue, being a subset of std::set, could be done with segment trees as well.
It might seems tricky to implement Dijkstra's algorithm in C.
But once you get used to it, it is kind of intuitive.
See this submission as an example.
Here, I have a distance array `d` and a segment tree of size `n`. d[n] is set to infinity for ease of implementation.
Now, construct a segment tree where the leaf node at position `i` stores the integer `i`. And when you `pull` a node in the segment tree, take the value of the child which distance is lower.
In each of n iterations in Dijkstra's algorithm, a unsettled node with least distance from the priority queue is taken. This can be done with taking the value at the root node of segment tree.
Once you settles shortest path to node `u` in Dijkstra's, update position `u` in the segment tree to `n`. This way, `u` is removed from the priority queue.
Everytime you relax an edge from u to v, just pull each ancestor node of the leaf node at position v.
deque
Deque is trivial to implement. Basically two pointer an a single array.
int q[100000], hd, tl;
void test_q()
{
/* here, the pointers are not initialized to zero
* because the push_back move tail pointer backward */
hd = tl = 50000;
q[hd++] = 2; /* push_front 2 to q */
q[hd++] = 3; /* push_front 3 to q */
q[hd++] = 4; /* push_front 4 to q */
q[hd++] = 5; /* push_front 5 to q */
int x = q[tl++]; /* pop_back */
int y = q[--hd]; /* pop_front */
q[--tl] = -3; /* push_back -3 to q */
}