ATCODER_
.__int128 / unsigned __int128(g++, clang++)
or _mul128 / _umul128(Visual Studio)
works.__builtin_(ctz/ctzll/clz/clzll/popcount)(g++, clang++)
or _BitScan(Forward/Reverse)(Visual Studio)
works.char / short / int / ll
and their unsigned
types (and signed char
) are 8 / 16 / 32 / 64
bits.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.
g++ main.cpp -std=c++14 -I /path/to/ac-library
(/path/to/ac-library
stands for the directory where the downloaded ac-library is located).atcoder
folder by the environment variable CPLUS_INCLUDE_PATH
as CPLUS_INCLUDE_PATH="/path/to/ac-library"
. (On Windows, type like C:\path\to\ac-library
in the field of the variable CPLUS_INCLUDE_PATH
on the Window of Environment Variables. Note that, you should use backslashes, not slashes.) Then, you can compile just by g++ main.cpp -std=c++14
.Visual Studio 2019 / 2022 is supported. Update it if you are using old Visual Studio.
If Visual Studio is installed, there is a folder like the following.
C:\Program Files\Microsoft Visual Studio\2022\(Community, Professional or Enterprise)\VC\Tools\MSVC\(Some number, e.g. 14.35.32215)\include
C:\Program Files (x86)\Microsoft Visual Studio\2019\(Community, Professional or Enterprise)\VC\Tools\MSVC\(Some number, e.g. 14.27.29110)\include
Copy atcoder
folder into it, i.e., put it so that the path will be as follows.
C:\Program Files\Microsoft Visual Studio\2022\(Community, Professional or Enterprise)\VC\Tools\MSVC\(Some number, e.g. 14.35.32215)\include\atcoder\dsu.hpp
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.
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.
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
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;
}
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;
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.
Constructors of structs except modint
are declared with the explicit specifier.
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.
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.
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.