GCC Code Coverage Report

Directory: src/
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 76.9% 50 / 0 / 65
Functions: 62.5% 5 / 0 / 8
Branches: 43.0% 40 / 16 / 109
level_ancestor.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include <algorithm>
4 #include <vector>
5 #include <cassert>
6
7 #include "yc.hpp"
8
9 namespace ecnerwala {
10
11 using std::swap;
12
13 struct level_ancestor {
14 int N;
15 std::vector<int> preorder;
16 std::vector<int> idx;
17 std::vector<std::pair<int, int>> heavyPar; // heavy parent, distance
18 ✗ level_ancestor() : N(0) {}
19
20
3/6
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 21 times.
✓ Branch 5 → 6 taken 21 times.
✓ Branch 6 → 7 taken 21 times.
✗ Branch 9 → 10 not taken.
✗ Branch 13 → 14 not taken.
 21 level_ancestor(const std::vector<int>& par) : N(int(par.size())), preorder(N), idx(N), heavyPar(N) {
21
1/2
✓ Branch 7 → 8 taken 21 times.
✗ Branch 17 → 18 not taken.
 21 std::vector<std::vector<int>> ch(N);
22
2/4
✓ Branch 12 → 9 taken 6612765 times.
✓ Branch 12 → 13 taken 21 times.
✗ Branch 26 → 20 not taken.
✗ Branch 26 → 27 not taken.
 6612786 for (int i = 0; i < N; i++) {
23
3/6
✓ Branch 9 → 10 taken 6612744 times.
✓ Branch 9 → 11 taken 21 times.
✓ Branch 10 → 11 taken 6612744 times.
✗ Branch 21 → 22 not taken.
✗ Branch 21 → 25 not taken.
✗ Branch 24 → 25 not taken.
 6612765 if (par[i] != -1) ch[par[i]].push_back(i);
24 }
25
1/2
✓ Branch 13 → 14 taken 21 times.
✗ Branch 29 → 30 not taken.
 21 std::vector<int> sz(N);
26 21 int nxt_idx = 0;
27
2/4
✓ Branch 20 → 15 taken 6612765 times.
✓ Branch 20 → 21 taken 21 times.
✗ Branch 40 → 32 not taken.
✗ Branch 40 → 41 not taken.
 6612786 for (int i = 0; i < N; i++) {
28
2/4
✓ Branch 15 → 16 taken 21 times.
✓ Branch 15 → 19 taken 6612744 times.
✗ Branch 33 → 34 not taken.
✗ Branch 33 → 39 not taken.
 6612765 if (par[i] == -1) {
29
1/2
✓ Branch 16 → 17 taken 21 times.
✗ Branch 34 → 35 not taken.
 21 std::y_combinator([&](auto self, int cur) -> void {
30 6612765 sz[cur] = 1;
31
2/4
✓ Branch 5 → 3 taken 6612744 times.
✓ Branch 5 → 6 taken 6612765 times.
✗ Branch 20 → 6 not taken.
✗ Branch 20 → 21 not taken.
 13225509 for (int nxt : ch[cur]) {
32
0/1
✗ Branch 8 → 9 not taken.
 6612744 self(nxt);
33 6612744 sz[cur] += sz[nxt];
34 }
35
2/4
✓ Branch 6 → 7 taken 3152019 times.
✓ Branch 6 → 8 taken 3460746 times.
✗ Branch 23 → 24 not taken.
✗ Branch 23 → 37 not taken.
 6612765 if (!ch[cur].empty()) {
36
2/3
void ecnerwala::level_ancestor::level_ancestor(std::vector<int, std::allocator<int> > const&)::{lambda(auto:1, int)#1}::operator()<std::reference_wrapper<std::y_combinator_result<{lambda(auto:1, int)#1}> > >(std::reference_wrapper<std::y_combinator_result<{lambda(auto:1, int)#1}> >, int) const:
✓ Branch 5 → 6 taken 492678 times.
✓ Branch 5 → 7 taken 2968047 times.
ecnerwala::level_ancestor::level_ancestor(std::vector<int, std::allocator<int> > const&)::{lambda(auto:1, int)#1}::operator()<std::reference_wrapper<std::y_combinator_result<{lambda(auto:1, int)#1}> > >(std::reference_wrapper<std::y_combinator_result<{lambda(auto:1, int)#1}> >, int) const::{lambda(int, int)#1}::operator()(int, int) const:
✗ Branch 28 → 29 not taken.
 6612744 auto mit = std::max_element(ch[cur].begin(), ch[cur].end(), [&](int a, int b) { return sz[a] < sz[b]; });
37 3152019 swap(*ch[cur].begin(), *mit);
38 }
39
0/1
✗ Branch 35 → 36 not taken.
 6612786 })(i);
40
0/1
✗ Branch 36 → 37 not taken.
 21 std::y_combinator([&](auto self, int cur, int isRoot = true) -> void {
41
2/2
✓ Branch 2 → 3 taken 3460746 times.
✓ Branch 2 → 6 taken 3152019 times.
 6612765 preorder[idx[cur] = nxt_idx++] = cur;
42
2/4
✓ Branch 2 → 3 taken 3460746 times.
✓ Branch 2 → 6 taken 3152019 times.
✗ Branch 4 → 5 not taken.
✗ Branch 4 → 16 not taken.
 6612765 if (isRoot) {
43
2/4
✓ Branch 3 → 4 taken 3460725 times.
✓ Branch 3 → 5 taken 21 times.
✗ Branch 6 → 7 not taken.
✗ Branch 6 → 10 not taken.
 3460746 heavyPar[idx[cur]] = {par[cur] == -1 ? -1 : idx[par[cur]], 1};
44 } else {
45 3152019 assert(idx[par[cur]] == idx[cur]-1);
46 3152019 heavyPar[idx[cur]] = heavyPar[idx[cur]-1];
47 3152019 heavyPar[idx[cur]].second++;
48 }
49 6612765 bool chRoot = false;
50
2/4
✓ Branch 12 → 10 taken 6612744 times.
✓ Branch 12 → 13 taken 6612765 times.
✗ Branch 44 → 32 not taken.
✗ Branch 44 → 45 not taken.
 13225509 for (int nxt : ch[cur]) {
51
0/1
✗ Branch 34 → 35 not taken.
 6612744 self(nxt, chRoot);
52 6612744 chRoot = true;
53 }
54
1/2
✓ Branch 17 → 18 taken 21 times.
✗ Branch 37 → 38 not taken.
 21 })(i);
55 }
56 }
57 21 }
58
59 7108683 int get_ancestor(int a, int k) const {
60 7108683 assert(k >= 0);
61 7108683 a = idx[a];
62
2/6
✓ Branch 10 → 5 taken 12179724 times.
✓ Branch 10 → 11 taken 7108683 times.
✗ Branch 17 → 18 not taken.
✗ Branch 17 → 19 not taken.
✗ Branch 18 → 6 not taken.
✗ Branch 18 → 19 not taken.
 19288407 while (a != -1 && k) {
63
2/4
✓ Branch 5 → 6 taken 7951617 times.
✓ Branch 5 → 8 taken 4228107 times.
✗ Branch 7 → 8 not taken.
✗ Branch 7 → 15 not taken.
 12179724 if (k >= heavyPar[a].second) {
64 7951617 k -= heavyPar[a].second;
65 7951617 assert(heavyPar[a].first <= a - heavyPar[a].second);
66 ✗ a = heavyPar[a].first;
67 } else {
68 4228107 a -= k;
69 4228107 k = 0;
70 }
71 }
72
1/4
✓ Branch 11 → 12 taken 7108683 times.
✗ Branch 11 → 13 not taken.
✗ Branch 19 → 20 not taken.
✗ Branch 19 → 21 not taken.
 7108683 if (a == -1) return -1;
73 7108683 else return preorder[a];
74 }
75
76 10000013 int lca(int a, int b) const {
77 10000013 a = idx[a], b = idx[b];
78 51221732 while (true) {
79
2/4
✓ Branch 3 → 4 taken 13484719 times.
✓ Branch 3 → 5 taken 37737013 times.
✗ Branch 5 → 6 not taken.
✗ Branch 5 → 7 not taken.
 51221732 if (a > b) swap(a, b);
80 51221732 assert(a <= b);
81
2/4
✓ Branch 7 → 8 taken 10000013 times.
✓ Branch 7 → 9 taken 41221719 times.
✗ Branch 10 → 11 not taken.
✗ Branch 10 → 13 not taken.
 51221732 if (a > b - heavyPar[b].second) {
82 10000013 return preorder[a];
83 }
84 41221719 b = heavyPar[b].first;
85
1/4
✓ Branch 9 → 3 taken 41221719 times.
✗ Branch 9 → 10 not taken.
✗ Branch 14 → 15 not taken.
✗ Branch 14 → 16 not taken.
 41221719 if (b == -1) return -1;
86 }
87 }
88
89 ✗ int dist(int a, int b) const {
90 ✗ a = idx[a], b = idx[b];
91 ✗ int res = 0;
92 while (true) {
93 ✗ if (a > b) swap(a, b);
94 ✗ assert(a <= b);
95 ✗ if (a > b - heavyPar[b].second) {
96 ✗ res += b - a;
97 ✗ break;
98 }
99 ✗ res += heavyPar[b].second;
100 ✗ b = heavyPar[b].first;
101 ✗ if (b == -1) return -1;
102 }
103 ✗ return res;
104 }
105 };
106
107 } // namespace ecnerwala
108