Trait BitDpExt

Source

pub trait BitDpExt:
    Sized
    + Copy
    + Default
    + PartialEq
    + Eq
    + PartialOrd
    + Ord
    + Not<Output = Self>
    + BitAnd<Output = Self>
    + BitOr<Output = Self>
    + BitXor<Output = Self>
    + Shl<usize, Output = Self>
    + Shr<usize, Output = Self>
    + Add<Output = Self>
    + Sub<Output = Self>
    + Div<Output = Self>
    + Zero
    + One {
    // Provided methods
    fn contains(self, x: usize) -> bool { ... }
    fn insert(self, x: usize) -> Self { ... }
    fn remove(self, x: usize) -> Self { ... }
    fn is_subset(self, elements: Self) -> bool { ... }
    fn is_superset(self, elements: Self) -> bool { ... }
    fn subsets(self) -> Subsets<Self> ⓘ { ... }
    fn combinations(n: usize, k: usize) -> Combinations<Self> ⓘ { ... }
}

Provided Methods§

Source

fn is_subset(self, elements: Self) -> bool

Examples found in repository ?

crates/competitive/src/algorithm/bitdp.rs (line 37)

36    fn is_superset(self, elements: Self) -> bool {
37        elements.is_subset(self)
38    }

Source

fn is_superset(self, elements: Self) -> bool

Source

fn subsets(self) -> Subsets<Self> ⓘ

Examples found in repository ?

crates/competitive/src/data_structure/submask_range_query.rs (line 86)

82    pub fn get_query(&self, m: u32) -> impl Iterator<Item = (u32, bool)> {
83        let fix = m & self.mask[0];
84        let sub = m & self.mask[1];
85        let sup = (!m) & self.mask[2];
86        sup.subsets().flat_map(move |s| {
87            let inv = s.count_ones() & 1 == 1;
88            sub.subsets().map(move |t| (fix | s | t, inv))
89        })
90    }
91
92    pub fn update_query(&self, m: u32) -> impl Iterator<Item = u32> {
93        let fix = m & self.mask[0] | m & self.mask[1];
94        let sup = (!m) & self.mask[0];
95        let sub = m & self.mask[2];
96        sub.subsets()
97            .flat_map(move |s| sup.subsets().map(move |t| fix | s | t))
98    }

More examples

Hide additional examples

crates/competitive/src/graph/steiner_tree.rs (line 33)

8    fn steiner_tree<'a, S, M, I>(
9        &self,
10        terminals: I,
11        weight: &'a M,
12    ) -> SteinerTreeOutput<'_, S, Self>
13    where
14        Self: VertexMap<S::T> + AdjacencyView<'a, M, S::T>,
15        S: ShortestPathSemiRing,
16        I: IntoIterator<Item = Self::VIndex> + ExactSizeIterator,
17    {
18        let tsize = terminals.len();
19        if tsize == 0 {
20            return SteinerTreeOutput {
21                g: self,
22                dp: vec![],
23            };
24        }
25        let mut dp: Vec<_> = repeat_with(|| self.construct_vmap(S::inf))
26            .take(1 << tsize)
27            .collect();
28        for (i, t) in terminals.into_iter().enumerate() {
29            *self.vmap_get_mut(&mut dp[1 << i], t) = S::source();
30        }
31        for bit in 1..1 << tsize {
32            for u in self.vertices() {
33                for sub in bit.subsets() {
34                    if sub != 0 {
35                        let cost =
36                            S::mul(self.vmap_get(&dp[sub], u), self.vmap_get(&dp[bit ^ sub], u));
37                        S::add_assign(self.vmap_get_mut(&mut dp[bit], u), &cost);
38                    }
39                }
40            }
41            let dp = &mut dp[bit];
42            let mut heap: BinaryHeap<_> = self
43                .vertices()
44                .map(|u| PartialIgnoredOrd(Reverse(self.vmap_get(dp, u).clone()), u))
45                .collect();
46            while let Some(PartialIgnoredOrd(Reverse(d), u)) = heap.pop() {
47                if self.vmap_get(dp, u) != &d {
48                    continue;
49                }
50                for a in self.aviews(weight, u) {
51                    let v = a.vindex();
52                    let nd = S::mul(&d, &a.avalue());
53                    if S::add_assign(self.vmap_get_mut(dp, v), &nd) {
54                        heap.push(PartialIgnoredOrd(Reverse(nd), v));
55                    }
56                }
57            }
58        }
59        SteinerTreeOutput { g: self, dp }
60    }