232-aka-pretty-pi 님의 블로그 232-aka-pretty-pi 님의 블로그

struct HopcroftKarp { int n; int m; int match_cnt; std::vector lft; std::vector rgt; std::vector> adj; HopcroftKarp(int n, int m) : n(n), m(m), match_cnt(0), lft(n, -1), rgt(m, -1), adj(n) { void(0); } void addEdge(int u, int v) { assert(0 lvl(n, -1); std::vector que; for (int i = 0; i bool { for (int x : adj[u]) { if (rgt[x] == -1 || (lvl[rgt[x]] == lv..

template struct MinCostMaxFlow { struct Edge { int from; int to; F cap; C cost; Edge(int from, int to, F cap, C cost) : from(from), to(to), cap(cap), cost(cost) { void(0); } }; int n; int s; int t; std::vector inq; std::vector from; // maybe change this vector's name to prv? it kinda collides with Edge::from std::vector dist; std::vector edges; std::vector> g; M..

will use only until I add hopcroft karp algorithm..struct BipartiteMatching { int n; int m; int match_cnt; std::vector lft; std::vector rgt; std::vector> adj; BipartiteMatching(int n, int m) : n(n), m(m), match_cnt(0), lft(n, -1), rgt(m, -1), adj(n) { void(0); } void addEdge(int l, int r) { assert(0 vis(n); auto dfs = [&](auto&& dfs, int u) -> bool { vis[u] = true; f..

template struct Dinic { struct Edge { int to; T cap; Edge(int to, T cap) : to(to), cap(cap) { void(0); } }; int n; int s; int t; std::vector lvl; std::vector ptr; std::vector edges; std::vector> g; Dinic(int n, int s, int t) : n(n), s(s), t(t), lvl(n), ptr(n), g(n) { assert(0 que(1, s); for (int b = 0; b 0 && lvl[to] == -1) { lvl[to] = lvl[que[b]] + 1;..

need PriorityQueuePair.template struct MinMaxPQ { PriorityQueuePair> minq; PriorityQueuePair maxq; [[nodiscard]] int size() const { return minq.size(); } [[nodiscard]] bool empty() const { return size() == 0; } void insert(const T& x) { minq.insert(x); maxq.insert(x); } [[nodiscard]] const T& getMin() const { assert(!empty()); return minq.get(); } [[nodiscard]] const..

struct Centroid { int n; std::vector> g; std::vector done; std::vector siz; Centroid(int n) : n(n), g(n), done(n), siz(n) { void(0); } const std::vector& operator[](int idx) const { assert(0 tot) { return getCentImpl(v, u, tot); } } return u; } int getCent(int u) { assert(0 par; CentroidTree(int n) : Centroid(n), par(n, -1) { void(0); } int work(int u ..

TODO : add ntt?template using Polynomial = std::vector;namespace polynomial { using F = long double; using complexF = std::complex; constexpr F pi = 3.1415926535897932L; void fft(std::vector& a) { int n = int(a.size()); for (int i = 1, rev_i = 0; i > 1; ; bit >>= 1) { if (((rev_i ^= bit) & bit) != 0) { break; } } if (i & a) { int n = int(a.size()); ..

namespace lcs_algo { using uint64 = unsigned long long; constexpr int B = 64; std::vector bitDP(const std::string& s, const std::string& t, const std::vector& id, int id_cnt) { int m = int(t.size()); int sz = (m + B - 1) / B; std::vector bs(id_cnt, std::vector(sz)); for (int i = 0; i dp(sz); for (const char& c : s) { const auto& on = bs[id[c]]; uint64 extra = 1; ..