Appendix / FAQ

Environments

How to Install

g++ / clang++

The easiest way is to put atcoder folder in the same place as main.cpp and execute g++ main.cpp -std=c++14 -I ., as noted in the index. Here, . is the symbol that represents the current directory (you should type a space and a period after I).

If you don't want to copy atcoder folder manually, do as follows.

Visual Studio

Visual Studio 2017 / 2019 is supported. Update it if you are using old Visual Studio.

If Visual Studio is installed, there is a folder like the following.

Copy atcoder folder into it, i.e., put it so that the path will be as follows.

How to Submit to Other Online Judge Systems

We prepared the script expander.py (python3.5 or later). The code combined.cpp, which can be compiled on other online judge systems, is generated by executing python3 expander.py main.cpp.

Although we tested it, we do not guarantee that it works correctly.

Preliminaries

💻Mark

This mark represents that the part, e.g., modint, may be difficult to use if you do not know much about C++. AC Library is designed to be still usable if you ignore the parts with this mark.

Template Function

For example, suffix_array(v) can take vector<int>, vector<ll>, et cetera as an argument. In this document, we unify these notations to suffix_array<T>(vector<T> v).

For example, to calculate the suffix array of the integral array $v$ stored in vector<int>, we can code as follows.

vector<int> sa = suffix_array(v);
// vector<int> sa = suffix_array<int>(v); : wrong usage

Default Constructor

The structs like scc_graph can be declared not only like the former code, but also like the latter code without initialization.

#include <atcoder/scc>;
using namespace atcoder;

int main() {
    int n;
    scanf("%d", &n);
    scc_graph g(n); // create the graph with n vertices
    return 0;
}

#include <atcoder/scc>;
using namespace atcoder;

scc_graph g;

int main() {
    return 0;
}

If it is declared in the latter way, the behavior (of the default constructor) is as follows.

You can also assign a value to the struct later.

#include <atcoder/scc>;
using namespace atcoder;

scc_graph g;

int main() {
    g = scc_graph(10);
    return 0;
}

The Type of the Edges

In the graph libraries, the type mf_graph<Cap>::edge is used to store edges.

For example, the type of the edges of mf_graph<int> is mf_graph<int>::edge. If you are not familiar to ::, you can use the string mf_graph<int>::edge in the same manner as int or string, like the following example.

vector<mf_graph<int>::edge> v;
mf_graph<int>::edge e;

Default Template Arguments

Sometimes the following notation is used, as in the document of convolution.

vector<T> convolution<int m = 998244353>(vector<T> a, vector<T> b)

It means the default template argument. As the following example, you can call the function without explicitly specifying m.

vector<long long> c = convolution(a, b);
vector<long long> c = convolution<924844033>(a, b);

In the first case, $m$ is automatically set to be $998244353$. In the second case, $m$ becomes the value that is explicitly specified, which is $924844033$ here.

💻 explicit specifier

Constructors of structs except modint are declared with the explicit specifier.

Precise requirements in Segtree / LazySegtree

In some situations, the cardinality of algebraic structures for Segtree / LazySegtree would be infinite. In precise meaning, it may break the constraints in the document.

For example, for the typical LazySegtree on $S = \mathrm{int}$ that processes the queries of range max and range addition, $S$ is not closed under addition due to the overflow. To resolve this problem, it is ensured to work correctly in the following situation.

Segtree

LazySegtree

Above LazySegtree can naturally be defined as follows, using infinite algebraic structures $S$ and $F$.

Under some sufficiently small constraints, it can be treated by this library by setting $(S', F')$ as follows.

The Behavior of maxflow

Internally, for each edge $e$, it stores the flow amount $f_e$ and the capacity $c_e$. Let $\mathrm{out}(v)$ and $\mathrm{in}(v)$ be the set of edges starts and ends at $v$, respectively. For each vertex $v$, let $g(v, f) = \sum_{e \in \mathrm{in}(v)}{f_e} - \sum_{e \in \mathrm{out}(v)}{f_e}$.

flow(s, t)

It changes the flow amount of each edge. Let $f_e$ and $f'_e$ be the flow amount of edge $e$ before and after calling it, respectively. Precisely, it changes the flow amount as follows.

min_cut(s)

The residual network is the graph whose edge set is given by gathering $(u, v)$ for each edge $e = (u, v, f_e, c_e)$ with $f_e \lt c_e$ and $(v, u)$ for each edge $e$ with $0 \lt f_e$. It returns the set of the vertices that is reachable from $s$ in the residual network.

change_edge(i, new_cap, new_flow)

It changes the flow amount and the capacity of the edge $i$ to new_flow and new_cap, respectively. It doesn't change other values.