This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://atcoder.jp/contests/abc237/tasks/abc237_Ex" #include <iostream> #include "library/graph/bipartite_matching.hpp" #include "library/string/palindromic_tree.hpp" using suisen::BipartiteMatching; using suisen::PalindromicTree; using suisen::PalindromicTreeVec; using suisen::PalindromicTreeArr; int main() { std::string s; std::cin >> s; std::vector<int> s2; for (char c : s) s2.push_back(c - 'a'); PalindromicTree<char, std::string> t(s); const int n = t.node_num() - 2; std::vector<int> par = t.parents(); BipartiteMatching matching(n, n); for (int i = 0; i < n; ++i) { int j = t.suffix_link(i + 2) - 2, k = par[i + 2] - 2; if (j >= 0) matching.add_edge(i, j); if (k >= 0) matching.add_edge(i, k); } std::cout << n - matching.solve() << std::endl; // verification of other versions of palindromic tree { PalindromicTreeVec<int> tv(s2); PalindromicTreeArr<int, 26> ta(s2); assert(par == tv.parents()); assert(par == ta.parents()); for (int i = 0; i < n + 2; ++i) { assert(t.suffix_link(i) == tv.suffix_link(i)); assert(t.suffix_link(i) == ta.suffix_link(i)); } } return 0; }
#line 1 "test/src/string/palindromic_tree/abc237_h.test.cpp" #define PROBLEM "https://atcoder.jp/contests/abc237/tasks/abc237_Ex" #include <iostream> #line 1 "library/graph/bipartite_matching.hpp" #include <algorithm> #include <cassert> #include <deque> #include <random> #include <utility> #include <vector> namespace suisen { struct BipartiteMatching { static constexpr int ABSENT = -1; BipartiteMatching() = default; BipartiteMatching(int n, int m) : _n(n), _m(m), _to_r(_n, ABSENT), _to_l(_m, ABSENT), _g(n + m) {} void add_edge(int fr, int to) { _g[fr].push_back(to), _f = -1; } // template <bool shuffle = true> // int solve_heuristics() { // if (_f >= 0) return _f; // static std::mt19937 rng(std::random_device{}()); // if constexpr (shuffle) for (auto& adj : _g) std::shuffle(adj.begin(), adj.end(), rng); // std::vector<int8_t> vis(_n, false); // auto dfs = [&, this](auto dfs, int u) -> bool { // if (std::exchange(vis[u], true)) return false; // for (int v : _g[u]) if (_to_l[v] == ABSENT) return _to_r[u] = v, _to_l[v] = u, true; // for (int v : _g[u]) if (dfs(dfs, _to_l[v])) return _to_r[u] = v, _to_l[v] = u, true; // return false; // }; // for (bool upd = true; std::exchange(upd, false);) { // vis.assign(_n, false); // for (int i = 0; i < _n; ++i) if (_to_r[i] == ABSENT) upd |= dfs(dfs, i); // } // return _f = _n - std::count(_to_r.begin(), _to_r.end(), ABSENT); // } int solve() { if (_f >= 0) return _f; const auto h = reversed_graph(); std::vector<int> level(_n + _m), iter(_n + _m); std::deque<int> que; auto bfs = [&] { for (int i = 0; i < _n; ++i) { if (_to_r[i] == ABSENT) level[i] = 0, que.push_back(i); else level[i] = -1; } std::fill(level.begin() + _n, level.end(), -1); bool ok = false; while (not que.empty()) { const int l = que.front(); que.pop_front(); for (int r : _g[l]) if (_to_r[l] != r and level[_n + r] < 0) { const int nl = _to_l[r]; level[_n + r] = level[l] + 1; if (nl == ABSENT) ok = true; else if (level[nl] < 0) level[nl] = level[l] + 2, que.push_back(nl); } } return ok; }; auto dfs = [&](auto dfs, const int r) -> bool { const int level_v = level[_n + r]; if (level_v < 0) return false; const int dr = h[r].size(); for (int &i = iter[_n + r]; i < dr; ++i) { const int l = h[r][i]; if (level_v <= level[l] or _to_l[r] == l or iter[l] > _m) continue; if (int nr = _to_r[l]; nr == ABSENT) { iter[l] = _m + 1, level[l] = _n + _m; _to_r[l] = r, _to_l[r] = l; return true; } else if (iter[l] <= nr) { iter[l] = nr + 1; if (level[l] > level[_n + nr] and dfs(dfs, nr)) { _to_r[l] = r, _to_l[r] = l; return true; } iter[l] = _m + 1, level[l] = _n + _m; } } return level[_n + r] = _n + _m, false; }; for (_f = 0; bfs();) { std::fill(iter.begin(), iter.end(), 0); for (int j = 0; j < _m; ++j) if (_to_l[j] == ABSENT) _f += dfs(dfs, j); } return _f; } std::vector<std::pair<int, int>> max_matching() { if (_f < 0) solve(); std::vector<std::pair<int, int>> res; res.reserve(_f); for (int i = 0; i < _n; ++i) if (_to_r[i] != ABSENT) res.emplace_back(i, _to_r[i]); return res; } std::vector<std::pair<int, int>> min_edge_cover() { auto res = max_matching(); std::vector<bool> vl(_n, false), vr(_n, false); for (const auto& [u, v] : res) vl[u] = vr[v] = true; for (int u = 0; u < _n; ++u) for (int v : _g[u]) if (not (vl[u] and vr[v])) { vl[u] = vr[v] = true; res.emplace_back(u, v); } return res; } std::vector<int> min_vertex_cover() { if (_f < 0) solve(); std::vector<std::vector<int>> g(_n + _m); std::vector<bool> cl(_n, true), cr(_m, false); for (int u = 0; u < _n; ++u) for (int v : _g[u]) { if (_to_r[u] == v) { g[v + _n].push_back(u); cl[u] = false; } else { g[u].push_back(v + _n); } } std::vector<bool> vis(_n + _m, false); std::deque<int> dq; for (int i = 0; i < _n; ++i) if (cl[i]) { dq.push_back(i); vis[i] = true; } while (dq.size()) { int u = dq.front(); dq.pop_front(); for (int v : g[u]) { if (vis[v]) continue; vis[v] = true; (v < _n ? cl[v] : cr[v - _n]) = true; dq.push_back(v); } } std::vector<int> res; for (int i = 0; i < _n; ++i) if (not cl[i]) res.push_back(i); for (int i = 0; i < _m; ++i) if (cr[i]) res.push_back(_n + i); return res; } std::vector<int> max_independent_set() { std::vector<bool> use(_n + _m, true); for (int v : min_vertex_cover()) use[v] = false; std::vector<int> res; for (int i = 0; i < _n + _m; ++i) if (use[i]) res.push_back(i); return res; } int left_size() const { return _n; } int right_size() const { return _m; } std::pair<int, int> size() const { return { _n, _m }; } int right(int l) const { assert(_f >= 0); return _to_r[l]; } int left(int r) const { assert(_f >= 0); return _to_l[r]; } const auto graph() const { return _g; } std::vector<std::vector<int>> reversed_graph() const { std::vector<std::vector<int>> h(_m); for (int i = 0; i < _n; ++i) for (int j : _g[i]) h[j].push_back(i); return h; } private: int _n, _m; std::vector<int> _to_r, _to_l; std::vector<std::vector<int>> _g; int _f = 0; }; } // namespace suisen #line 1 "library/string/palindromic_tree.hpp" #include <array> #line 7 "library/string/palindromic_tree.hpp" #include <map> namespace suisen { namespace internal::palindromic_tree { template <typename T> constexpr bool false_v = false; template <typename T, typename Sequence, typename ChildrenContainerType> struct PalindromicTreeBase { using container_type = Sequence; using value_type = T; using children_container_type = ChildrenContainerType; struct PalindromicTreeNode { friend struct PalindromicTreeBase; PalindromicTreeNode() = default; private: children_container_type _children; int _suffix_link; int _length; int _multiplicity; int _first_occurence; }; using node_type = PalindromicTreeNode; using node_pointer_type = node_type*; static constexpr int NODE_NULL = -1; static constexpr int NODE_M1 = 0; static constexpr int NODE_0 = 1; PalindromicTreeBase() { node_pointer_type node_m1 = _new_node(); node_m1->_suffix_link = NODE_M1; node_m1->_length = -1; node_m1->_first_occurence = 1; node_pointer_type node_0 = _new_node(); node_0->_suffix_link = NODE_M1; node_0->_length = 0; node_0->_first_occurence = 0; _active_index = 0; } template <typename Iterable> PalindromicTreeBase(const Iterable& seq) : PalindromicTreeBase() { add_all(seq); } int add(const value_type& val) { _seq.push_back(val); node_pointer_type par_node = _find_next_longest_suffix_palindrome(_get_node(_active_index)); auto& ch = par_node->_children; bool inserted = false; if constexpr (is_map) { const auto [it, inserted_tmp] = ch.emplace(val, _nodes.size()); inserted = inserted_tmp; _active_index = it->second; } else if constexpr (is_vector) { if (value_type(ch.size()) <= val) ch.resize(val + 1, NODE_NULL); if (ch[val] == NODE_NULL) { inserted = true; ch[val] = _nodes.size(); _active_index = _nodes.size(); } else { _active_index = ch[val]; } } else if constexpr (is_array) { if (ch[val] == NODE_NULL) { inserted = true; ch[val] = _nodes.size(); _active_index = _nodes.size(); } else { _active_index = ch[val]; } } else static_assert(false_v<void>); if (not inserted) { ++_get_node(_active_index)->_multiplicity; return _active_index; } int par_length = par_node->_length; int par_suffix_link = par_node->_suffix_link; node_pointer_type new_node = _new_node(); new_node->_multiplicity = 1; new_node->_length = par_length + 2; new_node->_first_occurence = _seq.size() - new_node->_length; if (new_node->_length == 1) { new_node->_suffix_link = NODE_0; } else { new_node->_suffix_link = _find_next_longest_suffix_palindrome(_get_node(par_suffix_link))->_children[val]; } return _active_index; } template <typename Iterable> void add_all(const Iterable &seq) { for (const auto &val : seq) add(val); } int node_num() const { return _nodes.size(); } const node_type& get_node(int index) const { return _nodes[index]; } int first_occurence(int index) const { return get_node(index)._first_occurence; } int length(int index) const { return get_node(index)._length; } int suffix_link(int index) const { return get_node(index)._suffix_link; } int node_multiplicity(int index) const { return get_node(index)._multiplicity; } const children_container_type& children(int index) const { return get_node(index)._children; } std::vector<int> parents() const { int sz = node_num(); std::vector<int> res(sz, -1); for (int i = 0; i < sz; ++i) { for (const auto& p : children(i)) { if constexpr (is_map) { res[p.second] = i; } else if (p != NODE_NULL) { res[p] = i; } } } return res; } const container_type get_palindrome(int index) { if (index == NODE_M1) return container_type{}; int l = first_occurence(index), r = l + length(index); return container_type{ _seq.begin() + l, _seq.begin() + r }; } std::vector<int> frequency_table() const { int sz = node_num(); std::vector<int> res(sz); for (int i = sz; i-- > 1;) { res[i] += node_multiplicity(i); res[suffix_link(i)] += res[i]; } return res; } template <bool erase_root = false> void clear() { _active_index = 0; _seq.clear(); if constexpr (erase_root) { _nodes.clear(); } else { _nodes.erase(_nodes.begin() + 2, _nodes.end()); } } void shrink_to_fit() { _seq.shrink_to_fit(); _nodes.shrink_to_fit(); } private: static constexpr bool is_map = std::is_same_v<std::map<value_type, int>, children_container_type>; static constexpr bool is_vector = std::is_same_v<std::vector<value_type>, children_container_type>; static constexpr bool is_array = std::is_same_v<std::array<value_type, std::tuple_size_v<children_container_type>>, children_container_type>; int _active_index; container_type _seq; std::vector<node_type> _nodes; node_pointer_type _new_node() { node_pointer_type new_node = &_nodes.emplace_back(); if constexpr (not (is_map or is_vector)) { std::fill(new_node->_children.begin(), new_node->_children.end(), NODE_NULL); } return new_node; } node_pointer_type _find_next_longest_suffix_palindrome(node_pointer_type node) { const int sz = _seq.size(); for (;; node = _get_node(node->_suffix_link)) { int opposite_index = sz - node->_length - 2; if (opposite_index >= 0 and _seq[opposite_index] == _seq.back()) return node; } } node_pointer_type _get_node(int index) { return &_nodes[index]; } }; } // namespace internal::palindromic_tree template <typename T, typename Sequence = std::vector<T>> struct PalindromicTree : public internal::palindromic_tree::PalindromicTreeBase<T, Sequence, std::map<T, int>> { using base_type = internal::palindromic_tree::PalindromicTreeBase<T, Sequence, std::map<T, int>>; using base_type::base_type; }; template <typename T, typename Sequence = std::vector<T>> struct PalindromicTreeVec : public internal::palindromic_tree::PalindromicTreeBase<T, Sequence, std::vector<T>> { using base_type = internal::palindromic_tree::PalindromicTreeBase<T, Sequence, std::vector<T>>; using base_type::base_type; }; template <typename T, std::size_t N, typename Sequence = std::vector<T>> struct PalindromicTreeArr : public internal::palindromic_tree::PalindromicTreeBase<T, Sequence, std::array<T, N>> { using base_type = internal::palindromic_tree::PalindromicTreeBase<T, Sequence, std::array<T, N>>; using base_type::base_type; }; } // namespace suisen #line 7 "test/src/string/palindromic_tree/abc237_h.test.cpp" using suisen::BipartiteMatching; using suisen::PalindromicTree; using suisen::PalindromicTreeVec; using suisen::PalindromicTreeArr; int main() { std::string s; std::cin >> s; std::vector<int> s2; for (char c : s) s2.push_back(c - 'a'); PalindromicTree<char, std::string> t(s); const int n = t.node_num() - 2; std::vector<int> par = t.parents(); BipartiteMatching matching(n, n); for (int i = 0; i < n; ++i) { int j = t.suffix_link(i + 2) - 2, k = par[i + 2] - 2; if (j >= 0) matching.add_edge(i, j); if (k >= 0) matching.add_edge(i, k); } std::cout << n - matching.solve() << std::endl; // verification of other versions of palindromic tree { PalindromicTreeVec<int> tv(s2); PalindromicTreeArr<int, 26> ta(s2); assert(par == tv.parents()); assert(par == ta.parents()); for (int i = 0; i < n + 2; ++i) { assert(t.suffix_link(i) == tv.suffix_link(i)); assert(t.suffix_link(i) == ta.suffix_link(i)); } } return 0; }