GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 18 / 0 / 18
Functions: 100.0% 5 / 0 / 5
Branches: 100.0% 18 / 0 / 18
src/tree/lca_hld/lib.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include "../dfs/info/lib.hpp"
4 #include "../dfs/top/lib.hpp"
5
6 namespace tifa_libs {
7
8 template <tree_c G>
9 struct lca_hld {
10 using tree_info_t = tree_dfs_info<G, tdi_dfn, tdi_maxson, tdi_dep, tdi_fa>;
11 tree_info_t info;
12 vecu top;
13
14 187 CEXP lca_hld(G CR tr) : info{tr} { top = tree_top(tr, info.dfn, info.maxson); }
15
16 23272749 CEXP u32 operator()(u32 u, u32 v) CNE {
17
8/8
tifa_libs::lca_hld<tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > > >::operator()(unsigned int, unsigned int) const:
✓ Branch 4 taken 8364918 times.
✓ Branch 5 taken 9809278 times.
✓ Branch 12 taken 18174196 times.
✓ Branch 13 taken 3833872 times.
tifa_libs::lca_hld<tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > > >::operator()(unsigned int, unsigned int) const:
✓ Branch 4 taken 59970807 times.
✓ Branch 5 taken 57656684 times.
✓ Branch 12 taken 117627491 times.
✓ Branch 13 taken 19438877 times.
 159074436 while (top[u] != top[v]) info.dep[top[u]] < info.dep[top[v]] ? v = info.fa[top[v]] : u = info.fa[top[u]];
18
4/4
tifa_libs::lca_hld<tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > > >::operator()(unsigned int, unsigned int) const:
✓ Branch 2 taken 1161885 times.
✓ Branch 3 taken 2671987 times.
tifa_libs::lca_hld<tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > > >::operator()(unsigned int, unsigned int) const:
✓ Branch 2 taken 5451698 times.
✓ Branch 3 taken 13987179 times.
 23272749 retif_((info.dep[u] > info.dep[v]), v, u);
19 }
20 8957832 CEXP ptt<vecptu> getchain(u32 u, u32 v) NE {
21 8957832 u32 lca = (*this)(u, v);
22 8957832 vecptu retu, retv;
23
2/2
✓ Branch 6 taken 30381426 times.
✓ Branch 7 taken 8957832 times.
 39339258 while (top[u] != top[lca]) retu.emplace_back(u, top[u]), u = info.fa[top[u]];
24 8957832 retu.emplace_back(u, lca);
25
2/2
✓ Branch 6 taken 31584900 times.
✓ Branch 7 taken 8957832 times.
 40542732 while (top[v] != top[lca]) retv.emplace_back(top[v], v), v = info.fa[top[v]];
26
2/2
✓ Branch 0 taken 4789866 times.
✓ Branch 1 taken 4167966 times.
 8957832 if (v != lca) retv.emplace_back(info.maxson[lca], v);
27 8957832 reverse(retv);
28 8957832 return {retu, retv};
29 8957832 }
30 };
31
32 } // namespace tifa_libs
33