diff options
author | Xiaoxu Guo <shimo11370@proton.me> | 2024-06-06 23:20:26 +0800 |
---|---|---|
committer | Xiaoxu Guo <shimo11370@proton.me> | 2024-06-06 23:20:26 +0800 |
commit | 8f7ef6bae03fca6698d9cd2eb330f01a6cc893b7 (patch) | |
tree | ee93dc2e682df768f8f176498dec4726094594d1 | |
parent | aa4179aaf33d6927bcc72b1c096bb5924668e5ad (diff) | |
download | shoka-8f7ef6bae03fca6698d9cd2eb330f01a6cc893b7.tar.gz shoka-8f7ef6bae03fca6698d9cd2eb330f01a6cc893b7.zip |
fixed
-rw-r--r-- | eulerian_tour.h | 38 | ||||
-rw-r--r-- | primality_test.h | 5 | ||||
-rw-r--r-- | reroot_dp.h | 2 |
3 files changed, 23 insertions, 22 deletions
diff --git a/eulerian_tour.h b/eulerian_tour.h index 7256adb..8b60cfe 100644 --- a/eulerian_tour.h +++ b/eulerian_tour.h @@ -1,23 +1,7 @@ #include <utility> #include <vector> -struct EulerianTour : public std::vector<int> { - explicit EulerianTour(int n_, int s, - const std::vector<std::pair<int, int>> &edges_) - : n{n_}, m(edges_.size()), head(n, -1), next(m << 1), - used(m), edges{edges_} { - for (int i = 0; i < m << 1; ++i) { - auto [u, v] = edges[i >> 1]; - if (i & 1) { - std::swap(u, v); - } - next[i] = head[u]; - head[u] = i; - } - dfs(s); - } - -private: +class Eulerian { void dfs(int u) { while (~head[u]) { int i = head[u]; @@ -28,11 +12,29 @@ private: dfs(v); } } - push_back(u); + tour.push_back(u); } int n, m; std::vector<int> head, next; std::vector<bool> used; const std::vector<std::pair<int, int>> &edges; + +public: + explicit Eulerian(int n_, int s, + const std::vector<std::pair<int, int>> &edges_) + : n{n_}, m(edges_.size()), head(n, -1), next(m << 1), used(m), + edges{edges_} { + for (int i = 0; i < m << 1; ++i) { + auto [u, v] = edges[i >> 1]; + if (i & 1) { + std::swap(u, v); + } + next[i] = head[u]; + head[u] = i; + } + dfs(s); + } + + std::vector<int> tour; }; diff --git a/primality_test.h b/primality_test.h index 3123317..dd0ec9f 100644 --- a/primality_test.h +++ b/primality_test.h @@ -1,9 +1,8 @@ #pragma once -#include <type_traits> +#include <concepts> -template <typename T> static inline constexpr T is_prime(T n) { - static_assert(std::is_integral_v<T>); +template <std::integral T> static inline constexpr T is_prime(T n) { if (n < 2) { return false; } diff --git a/reroot_dp.h b/reroot_dp.h index 605a5f3..07ee821 100644 --- a/reroot_dp.h +++ b/reroot_dp.h @@ -6,7 +6,7 @@ template <IsTreeMonoid M, IsGraph Tree> requires std::is_same_v<GraphEdge<Tree>, std::pair<int, M>> -class RerootDp { +class RerootDp : public std::vector<M> { void dfs_down(int p, int u) { for (auto &&[v, e] : tree[u]) { if (v != p) { |