src/tree/dfs/top/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../util/alias/others/lib.hpp" | ||
| 4 | #include "../../ds/lib.hpp" | ||
| 5 | |||
| 6 | namespace tifa_libs { | ||
| 7 | |||
| 8 | template <tree_c G, bool need_dfn = false> | ||
| 9 | 530 | CEXP vecu tree_top(G CR tr, std::conditional_t<need_dfn, vecu&, spnu> dfn, spnu maxson) NE { | |
| 10 | 530 | cu32 n = tr.vsize(); | |
| 11 | 686 | if CEXP (need_dfn) dfn = vecu(n); | |
| 12 | 530 | vecu top(n, n); | |
| 13 | 530 | u32 cnt = 0; // NOLINT(misc-const-correctness) | |
| 14 | 66083313 | auto f = [&](auto&& f, u32 u, u32 top_) NE -> void { | |
| 15 | 39570822 | if CEXP (need_dfn) dfn[u] = cnt++; | |
| 16 |
10/10<unknown function 9>:
✓ Branch 3 taken 8195268 times.
✓ Branch 4 taken 19816536 times.
✓ Branch 8 taken 4097634 times.
✓ Branch 9 taken 9908268 times.
void tifa_libs::tree_top<tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > >, false>(tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > > const&, std::conditional<false, std::vector<unsigned int, std::allocator<unsigned int> >&, std::span<unsigned int const, 18446744073709551615ul> >::type, std::span<unsigned int const, 18446744073709551615ul>)::{lambda(auto:1&&, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int)#1}&, unsigned int, unsigned int) const:
✓ Branch 3 taken 510966 times.
✓ Branch 4 taken 991144 times.
void tifa_libs::tree_top<tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >, false>(tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > > const&, std::conditional<false, std::vector<unsigned int, std::allocator<unsigned int> >&, std::span<unsigned int const, 18446744073709551615ul> >::type, std::span<unsigned int const, 18446744073709551615ul>)::{lambda(auto:1&&, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int)#1}&, unsigned int, unsigned int) const:
✓ Branch 3 taken 3014923 times.
✓ Branch 4 taken 7989026 times.
void tifa_libs::tree_top<tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >, true>(tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > > const&, std::conditional<true, std::vector<unsigned int, std::allocator<unsigned int> >&, std::span<unsigned int const, 18446744073709551615ul> >::type, std::span<unsigned int const, 18446744073709551615ul>)::{lambda(auto:1&&, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int)#1}&, unsigned int, unsigned int) const:
✓ Branch 3 taken 3526050 times.
✓ Branch 4 taken 8032968 times.
|
66082783 | if (top[u] = top_; maxson[u] == tr.vsize()) return; |
| 17 |
10/10<unknown function 9>:
✓ Branch 8 taken 47827860 times.
✓ Branch 9 taken 19816536 times.
✓ Branch 18 taken 23913930 times.
✓ Branch 19 taken 9908268 times.
void tifa_libs::tree_top<tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > >, false>(tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > > const&, std::conditional<false, std::vector<unsigned int, std::allocator<unsigned int> >&, std::span<unsigned int const, 18446744073709551615ul> >::type, std::span<unsigned int const, 18446744073709551615ul>)::{lambda(auto:1&&, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int)#1}&, unsigned int, unsigned int) const:
✓ Branch 8 taken 2493234 times.
✓ Branch 9 taken 991144 times.
void tifa_libs::tree_top<tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >, false>(tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > > const&, std::conditional<false, std::vector<unsigned int, std::allocator<unsigned int> >&, std::span<unsigned int const, 18446744073709551615ul> >::type, std::span<unsigned int const, 18446744073709551615ul>)::{lambda(auto:1&&, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int)#1}&, unsigned int, unsigned int) const:
✓ Branch 8 taken 18992862 times.
✓ Branch 9 taken 7989026 times.
void tifa_libs::tree_top<tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >, true>(tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > > const&, std::conditional<true, std::vector<unsigned int, std::allocator<unsigned int> >&, std::span<unsigned int const, 18446744073709551615ul> >::type, std::span<unsigned int const, 18446744073709551615ul>)::{lambda(auto:1&&, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int)#1}&, unsigned int, unsigned int) const:
✓ Branch 8 taken 17035082 times.
✓ Branch 9 taken 8032968 times.
|
157000910 | for (f(f, maxson[u], top_); auto v : tr[u]) |
| 18 |
10/10<unknown function 9>:
✓ Branch 3 taken 8195028 times.
✓ Branch 4 taken 39632832 times.
✓ Branch 11 taken 4097514 times.
✓ Branch 12 taken 19816416 times.
void tifa_libs::tree_top<tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > >, false>(tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > > const&, std::conditional<false, std::vector<unsigned int, std::allocator<unsigned int> >&, std::span<unsigned int const, 18446744073709551615ul> >::type, std::span<unsigned int const, 18446744073709551615ul>)::{lambda(auto:1&&, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int)#1}&, unsigned int, unsigned int) const:
✓ Branch 3 taken 510956 times.
✓ Branch 4 taken 1982278 times.
void tifa_libs::tree_top<tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >, false>(tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > > const&, std::conditional<false, std::vector<unsigned int, std::allocator<unsigned int> >&, std::span<unsigned int const, 18446744073709551615ul> >::type, std::span<unsigned int const, 18446744073709551615ul>)::{lambda(auto:1&&, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int)#1}&, unsigned int, unsigned int) const:
✓ Branch 3 taken 3014866 times.
✓ Branch 4 taken 15977996 times.
void tifa_libs::tree_top<tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >, true>(tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > > const&, std::conditional<true, std::vector<unsigned int, std::allocator<unsigned int> >&, std::span<unsigned int const, 18446744073709551615ul> >::type, std::span<unsigned int const, 18446744073709551615ul>)::{lambda(auto:1&&, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int)#1}&, unsigned int, unsigned int) const:
✓ Branch 3 taken 3525947 times.
✓ Branch 4 taken 13509135 times.
|
110262968 | if (top[(u32)v] == tr.vsize()) f(f, (u32)v, (u32)v); |
| 19 | }; | ||
| 20 | 530 | f(f, tr.root, tr.root); | |
| 21 | 530 | return top; | |
| 22 | } | ||
| 23 | |||
| 24 | } // namespace tifa_libs | ||
| 25 |