This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub tkmst201/Library
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/challenges/sources/VPC/Hupc/2871?year=2018" #include "GraphTheory/EulerTour.hpp" #include "DataStructure/DynamicSegmentTree.hpp" #include <cstdio> #include <utility> int main() { int N, Q; scanf("%d %d", &N, &Q); EulerTour<false>::Graph g(N); for (int i = 1; i < N; ++i) { int p; scanf("%d", &p); g[p - 1].emplace_back(i); } EulerTour<false> et(g, 0); DynamicSegmentTree<int> seg(et.size(), 0, [](auto x, auto y) { return x + y; }); auto segr = seg; for (int i = 0; i < N; ++i) { char c; scanf(" %c", &c); if (c == 'G') seg.set(et.in(i), 1); else segr.set(et.in(i), 1); } while (Q--) { int v; scanf("%d", &v); --v; seg.swap(segr, et.in(v), et.out(v)); const int x = seg.fold_all(); const int y = N - x; puts(x > y ? "broccoli" : "cauliflower"); } }
#line 1 "Test/DynamicSegmentTree.swap.test.cpp" #define PROBLEM "https://onlinejudge.u-aizu.ac.jp/challenges/sources/VPC/Hupc/2871?year=2018" #line 1 "GraphTheory/EulerTour.hpp" #include <vector> #include <cassert> #include <stack> #include <utility> /** * @brief https://tkmst201.github.io/Library/GraphTheory/EulerTour.hpp */ template<bool EDGE> struct EulerTour { using size_type = std::size_t; using Graph = std::vector<std::vector<int>>; private: int n, root; std::vector<int> in_, out_, par_, g_idx; public: EulerTour(const Graph & g, int root = 0) : n(g.size()), root(root), in_(size(), -1), out_(size(), -1), par_(n, -1), g_idx(n << 1, -1) { std::stack<std::pair<int, int>> stk; int num = 0; in_[root] = num++; stk.emplace(root, 0); while (!stk.empty()) { const auto [u, i] = stk.top(); stk.pop(); if (i < g[u].size()) { const int v = g[u][i]; assert(0 <= v && v < n); assert(v != u); stk.emplace(u, i + 1); if (v == par_[u]) g_idx[u << 1 | 1] = i; else { in_[v] = num++; par_[v] = u; g_idx[v << 1] = i; stk.emplace(v, 0); } } else { out_[u] = num; if (EDGE) ++num; } } } size_type size() const noexcept { return EDGE ? n << 1 : n; } int par(int k) const noexcept { assert(0 <= k && k < n); return par_[k]; } int in(int k) const noexcept { assert(0 <= k && k < n); return in_[k]; } int out(int k) const noexcept { assert(0 <= k && k < n); return out_[k]; } std::pair<int, int> par_from(int k) const noexcept { assert(0 <= k && k < n); return {par_[k], g_idx[k << 1]}; } int par_to(int k) const noexcept { assert(0 <= k && k < n); return g_idx[k << 1 | 1]; } }; #line 1 "DataStructure/DynamicSegmentTree.hpp" #include <functional> #line 7 "DataStructure/DynamicSegmentTree.hpp" #include <cstdint> /** * @brief https://tkmst201.github.io/Library/DataStructure/DynamicSegmentTree.hpp */ template<typename T> struct DynamicSegmentTree { using value_type = T; using const_reference = const value_type &; using size_type = std::size_t; using F = std::function<value_type (const_reference, const_reference)>; private: struct Node; using node_ptr = Node *; using const_ptr = const Node * const; struct Node { value_type val; node_ptr child[2] {nullptr, nullptr}; Node() = default; Node(const_reference val) : val(val) {} }; template<typename U> struct Data { U node; size_type l, r; Data(U node, size_type l, size_type r) : node(node), l(l), r(r) {} }; private: size_type n, n_; int log_n; value_type id_elem; F f; node_ptr root = nullptr; public: DynamicSegmentTree(size_type n, const_reference id_elem, const F & f) : n(n), id_elem(id_elem), f(f), root(nullptr) { n_ = 1; log_n = 0; while (n_ < n) n_ <<= 1, ++log_n; } DynamicSegmentTree(const DynamicSegmentTree & rhs) { *this = rhs; } DynamicSegmentTree(DynamicSegmentTree && rhs) { *this = std::forward<DynamicSegmentTree>(rhs); } ~DynamicSegmentTree() { clear(); } DynamicSegmentTree & operator =(const DynamicSegmentTree & rhs) { if (this != &rhs) { clear(); n = rhs.n; n_ = rhs.n_; log_n = rhs.log_n; id_elem = rhs.id_elem; f = rhs.f; root = copy_dfs(rhs.root, nullptr); } return *this; } DynamicSegmentTree & operator =(DynamicSegmentTree && rhs) { if (this != &rhs) { clear(); n = rhs.n; n_ = rhs.n_; log_n = rhs.log_n; id_elem = rhs.id_elem; f = rhs.f; root = rhs.root; rhs.root = nullptr; } return *this; } void clear() { clear_subtree(root); root = nullptr; } void clear(size_type l, size_type r) { assert(l <= r); assert(r <= size()); if ((l == 0 && r == n_) || n_ == 1) { clear(); return; } if (l == r || !root) return; std::stack<Data<node_ptr>> stk; stk.emplace(root, 0, n_); while (!stk.empty()) { auto [node, cl, cr] = stk.top(); stk.pop(); if (cl == cr) { node->val = f(node->child[0] ? node->child[0]->val : id_elem, node->child[1] ? node->child[1]->val : id_elem); continue; } const size_type m = cl + ((cr - cl) >> 1); stk.emplace(node, 0, 0); if (m < r && node->child[1]) { if (l <= m && cr <= r) { clear_subtree(node->child[1]); node->child[1] = nullptr; } else stk.emplace(node->child[1], m, cr); } if (l < m && node->child[0]) { if (l <= cl && m <= r) { clear_subtree(node->child[0]); node->child[0] = nullptr; } else stk.emplace(node->child[0], cl, m); } } } size_type size() const noexcept { return n; } void set(size_type k, const_reference x) { assert(k < size()); if (!root) root = new Node; node_ptr node = root; std::stack<node_ptr> stk; for (int i = log_n - 1; i >= 0; --i) { stk.emplace(node); const bool r = k >> i & 1; if (!node->child[r]) node->child[r] = new Node; node = node->child[r]; } node->val = x; while (!stk.empty()) { node = stk.top(); stk.pop(); node->val = f(node->child[0] ? node->child[0]->val : id_elem, node->child[1] ? node->child[1]->val : id_elem); } } value_type get(size_type k) const noexcept { assert(k < size()); if (!root) return id_elem; node_ptr node = root; for (int i = log_n - 1; i >= 0; --i) { const bool r = k >> i & 1; if (!node->child[r]) return id_elem; node = node->child[r]; } return node->val; } value_type fold(size_type l, size_type r) const noexcept { assert(l <= r); assert(r <= size()); if (l == r || !root) return id_elem; value_type res = id_elem; std::stack<Data<node_ptr>> stk; stk.emplace(root, 0, n_); while (!stk.empty()) { auto [node, cl, cr] = stk.top(); stk.pop(); if (l <= cl && cr <= r) res = f(res, node->val); else { const size_type m = cl + ((cr - cl) >> 1); if (m < r && node->child[1]) stk.emplace(node->child[1], m, cr); if (l < m && node->child[0]) stk.emplace(node->child[0], cl, m); } } return res; } value_type fold_all() const noexcept { if (!root) return id_elem; return root->val; } void swap(DynamicSegmentTree & rhs, size_type l, size_type r) { assert(size() == rhs.size()); assert(id_elem == rhs.id_elem); assert(l <= r); assert(r <= size()); if (this == &rhs) return; if (l == r) return; if ((l == 0 && r == n_) || n_ == 1) { std::swap(root, rhs.root); return; } if (!root && !rhs.root) return; if (!root) root = new Node{id_elem}; if (!rhs.root) rhs.root = new Node{id_elem}; std::stack<Data<std::pair<node_ptr, node_ptr>>> stk; stk.emplace(std::make_pair(root, rhs.root), 0, n_); while (!stk.empty()) { auto [nodes, cl, cr] = stk.top(); auto [node1, node2] = nodes; stk.pop(); if (cl == cr) { node1->val = f(node1->child[0] ? node1->child[0]->val : id_elem, node1->child[1] ? node1->child[1]->val : id_elem); node2->val = f(node2->child[0] ? node2->child[0]->val : id_elem, node2->child[1] ? node2->child[1]->val : id_elem); continue; } const size_type m = cl + ((cr - cl) >> 1); stk.emplace(nodes, 0, 0); if (m < r && (node1->child[1] || node2->child[1])) { if (l <= m && cr <= r) std::swap(node1->child[1], node2->child[1]); else { if (!node1->child[1]) node1->child[1] = new Node; else if (!node2->child[1]) node2->child[1] = new Node; stk.emplace(std::make_pair(node1->child[1], node2->child[1]), m, cr); } } if (l < m && (node1->child[0] || node2->child[0])) { if (l <= cl && m <= r) std::swap(node1->child[0], node2->child[0]); else { if (!node1->child[0]) node1->child[0] = new Node; else if (!node2->child[0]) node2->child[0] = new Node; stk.emplace(std::make_pair(node1->child[0], node2->child[0]), cl, m); } } } } private: node_ptr copy_dfs(const_ptr q, node_ptr r) { if (!q) return nullptr; node_ptr res = new Node{q->val}; res->child[0] = copy_dfs(q->child[0], res); res->child[1] = copy_dfs(q->child[1], res); return res; } void clear_subtree(node_ptr r) { if (!r) return; std::stack<node_ptr> stk; stk.emplace(r); while (!stk.empty()) { node_ptr node = stk.top(); stk.pop(); if (node->child[0]) stk.emplace(node->child[0]); if (node->child[1]) stk.emplace(node->child[1]); delete node; } } }; #line 5 "Test/DynamicSegmentTree.swap.test.cpp" #include <cstdio> #line 8 "Test/DynamicSegmentTree.swap.test.cpp" int main() { int N, Q; scanf("%d %d", &N, &Q); EulerTour<false>::Graph g(N); for (int i = 1; i < N; ++i) { int p; scanf("%d", &p); g[p - 1].emplace_back(i); } EulerTour<false> et(g, 0); DynamicSegmentTree<int> seg(et.size(), 0, [](auto x, auto y) { return x + y; }); auto segr = seg; for (int i = 0; i < N; ++i) { char c; scanf(" %c", &c); if (c == 'G') seg.set(et.in(i), 1); else segr.set(et.in(i), 1); } while (Q--) { int v; scanf("%d", &v); --v; seg.swap(segr, et.in(v), et.out(v)); const int x = seg.fold_all(); const int y = N - x; puts(x > y ? "broccoli" : "cauliflower"); } }