cp-includes

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub rsalesc/cp-includes

:warning: matroid/v2/EdgeFinder.cpp

Depends on

Required by

Code

#ifndef _LIB_EDGE_FINDER
#define _LIB_EDGE_FINDER
#include <bits/stdc++.h>
#include "Matroid.cpp"
#include "../../Lambda.cpp"

namespace lib {
  using namespace std;
namespace matroid {

template<typename M, typename F>
auto incremental_edge_finder(
  M& m,
  const lambda::Subset& sI,
  const lambda::SubsetFilter& I,
  int v,
  F && test) {
  return [&, v, test, done=0, ans=vector<int>()] () mutable {
    if(v < I.size() && !I(v)) {
      // CASE 1: v is an element not in IS.
      // In this case, should add v and remove a neighbor.
      m.clear();
      // First of all, add v.
      if(!m.check(v)) return -1;
      m.add(v);
      // Now add IS elements that aren't in B. These can't be removed.
      for(int i : sI.items()) {
        if(test(i)) continue;
        if(!m.check(i)) return -1;
        m.add(i);
      }
      // Finally, add IS elements that ARE in B. 
      for(int i : sI.items()) {
        if(!test(i)) continue;
        if(!m.check(i)) {
          // Introducing i and every element that comes next
          // makes this a circuit, that can be made independent by removing i.
          return i;
        }
        m.add(i);
      }
      // Element can be added directly, with no exchange.
      return I.size();
    }
    // CASE 2: v is source or an element in IS.
    if(!done) {
      // In this case, we should try adding elements after removing v.
      m.clear();
      for(int i : sI.items())
        if(i != v) m.add(i);
      for(int i = 0; i < I.size(); i++)
        if(!I(i) && test(i) && m.check(i))
          ans.push_back(i);
    }
    if(done < ans.size()) return ans[done++];
    return -1;
  };
}

template<typename M, typename F>
auto rank_edge_finder(
  M& m,
  const lambda::Subset& sI,
  const lambda::SubsetFilter& I,
  int v,
  F && test) {

  // Fast SubsetFilter.
  static vector<int> mask(1);
  int n = mask.size();
  while(n < I.size()) n *= 2;
  mask.assign(n, 0);

  auto filter = lambda::SubsetFilter(I.size(), [](int i) {
    return mask[i];
  });
  const static auto subset_mask = [](const lambda::Subset& s) {
    for(int i : s.items())
      mask[i] = true;
  };
  const static auto clear_mask = [](const lambda::Subset& s) {
    for(int i : s.items())
      mask[i] = false;
  };

  return [&, v, test, filter, sub=lambda::Subset()] () mutable {
    vector<int> need, extra;
    if(v < I.size() && !I(v)) {
      // CASE 1: v NOT in IS.
      // `need` will be v + elements that are in IS
      // but are not in B. Thus, they can't be part of
      // an exchange.
      // `extra` will be elements of IS that are in B.
      need.push_back(v);
      for(auto i : sI.items())
        if(!test(i)) need.push_back(i);
        else extra.push_back(i);

      auto check = [&](int mid) {
        need.insert(need.end(), extra.begin(), extra.begin() + mid);
        swap(sub.map, need);
        subset_mask(sub);
        int res = m.rank(sub, filter);
        clear_mask(sub);
        swap(sub.map, need);
        need.erase(need.end() - mid, need.end());
        return res == need.size() + mid;
      };

      // Binary search on element that makes up the circuit.
      if(!check(0)) return -1;
      if(check(extra.size())) return I.size();
      int l = 0, r = extra.size() + 1;
      while(l < r) {
        int mid = (l+r)/2;
        if(!check(mid))
          r = mid;
        else l = mid + 1;
      }
      if(l == extra.size() + 1) return I.size();
      return extra[l-1];
    }

    // CASE 2: v in IS.
    for(int i : sI.items())
      if(i != v) need.push_back(i);
    for(int i = 0; i < I.size(); i++)
      if(!I(i) && test(i)) extra.push_back(i);
    auto check = [&](int l, int r) {
      need.insert(need.end(), extra.begin() + l, extra.begin() + r);
      swap(sub.map, need);
      subset_mask(sub);
      int res = m.rank(sub, filter);
      clear_mask(sub);
      swap(sub.map, need);
      need.erase(need.end() - (r - l), need.end());
      return res > need.size();
    };

    int l = 0, r = extra.size();
    if(!check(l, r)) return -1;
    while(l < r) {
      int mid = (l+r)/2;
      if(check(l, mid+1))
        r = mid;
      else l = mid + 1;
    }
    return extra[l];
  };
}

} // namespace matroid
} // namespace lib

#endif
#line 1 "matroid/v2/EdgeFinder.cpp"


#include <bits/stdc++.h>
#line 1 "matroid/v2/Matroid.cpp"


#line 1 "Lambda.cpp"


#line 1 "Traits.cpp"


#line 4 "Traits.cpp"

namespace lib {
using namespace std;
namespace traits {

template <typename...> struct make_void { using type = void; };

template <typename... T> using void_t = typename make_void<T...>::type;

/// keep caide
template <typename Iterator>
using IteratorCategory = typename iterator_traits<Iterator>::iterator_category;

/// keep caide
template <typename Container>
using IteratorCategoryOf = IteratorCategory<typename Container::iterator>;

/// keep caide
template <typename Iterator>
using IteratorValue = typename iterator_traits<Iterator>::value_type;

/// keep caide
template <typename Container>
using IteratorValueOf = IteratorValue<typename Container::iterator>;

/// keep caide
template <typename Iterator>
using IsRandomIterator =
    is_base_of<random_access_iterator_tag, IteratorCategory<Iterator>>;

/// keep caide
template <typename Iterator>
using IsInputIterator =
    is_base_of<input_iterator_tag, IteratorCategory<Iterator>>;

/// keep caide
template <typename Iterator>
using IsBidirectionalIterator =
    is_base_of<bidirectional_iterator_tag, IteratorCategory<Iterator>>;

/// keep caide
template <typename Container>
using HasRandomIterator =
    is_base_of<random_access_iterator_tag, IteratorCategoryOf<Container>>;

/// keep caide
template <typename Container>
using HasInputIterator =
    is_base_of<input_iterator_tag, IteratorCategoryOf<Container>>;

/// keep caide
template <typename Container>
using HasBidirectionalIterator =
    is_base_of<bidirectional_iterator_tag, IteratorCategoryOf<Container>>;
} // namespace traits
} // namespace lib


#line 5 "Lambda.cpp"

namespace lib {
  using namespace std;
namespace lambda {
  using namespace traits;

const auto identity = [](int i) -> int { return i; };
const auto all = [](int i) -> bool { return true; };
const auto none = [](int i) -> bool { return false; };

auto first_n(int n) {
  return [n](int i) -> bool { return i < n; };
}

template<typename F, typename I = int>
using ValueType = decltype(declval<F>()(declval<I>()));

template<typename T>
struct Map {
  std::function<T(int)> f;
  Map() {}
  template<typename F>
  Map(const F& f_) : f(f_) {}
  T operator()(int i) const {
    return f(i);
  }
};

struct Subset;

template<typename T>
struct SubsetMap : Map<T> {
  using Map<T>::operator();
  using Map<T>::f;

  int n;
  SubsetMap() : Map<T>(), n(0) {}
  template<typename F>
  SubsetMap(int n, F && f_) : Map<T>(f_), n(n) {}
  int size() const { return n; }
  int count() const {
    int cnt = 0;
    for(int i = 0; i < n; i++)
      cnt += f(i) != 0;
    return cnt;
  }
  vector<T> operator()() const {
    vector<T> res(n);
    for(int i = 0; i < n; i++)
      res[i] = f(i);
    return res;
  }

  Subset as_subset() const;

  template<typename U = T,
           enable_if_t<is_same<U, bool>::value>* = nullptr>
  SubsetMap<T> operator!() const {
    return SubsetMap<T>(n, [f=f](int i) { return !f(i); });
  }

  template<typename U = T,
           enable_if_t<is_same<U, bool>::value>* = nullptr>
  SubsetMap<T> operator|(const SubsetMap<T>& rhs) const {
    return SubsetMap<T>(n, [f=f, g=rhs.f](int i) { return f(i) || g(i); });
  }

  SubsetMap<T> operator+(const SubsetMap<T>& rhs) const {
    int N = size() + rhs.size();
    return SubsetMap<T>(N, [n=n, f=f, g=rhs.f](int i) {
      return i >= n ? g(i - n) : f(i);
    });
  }

  SubsetMap<T> operator*(const SubsetMap<T>& rhs) const {
    return SubsetMap<T>(n, [f=f, g=rhs.f](int i) {
      return f(g(i));
    });
  }
};

struct Subset {
  mutable vector<int> map;
  Subset() {}
  Subset(const vector<int>& map_) : map(map_) {
  }
  void add(int i) {
    map.push_back(i);
  }
  void pop() { map.pop_back(); }
  void clear() { map.clear(); }
  int size() const { return map.size(); }
  int operator()(int i) const { return map[i]; }
  vector<int> items() const { return map; }

  template<typename F>
  SubsetMap<ValueType<F>> take_from(F && g) const {
    using T = ValueType<F>;
    auto map_ = map;
    return SubsetMap<T>(map.size(), [g, map_](int i) -> T {
      return g(map_[i]);
    });
  }

  Subset take_subset(const Subset& s) const {
    vector<int> res;
    for(int i : items()) {
      res.push_back(s(i));
    }
    return Subset(res);
  }

  SubsetMap<int> take_indices() const {
    return take_from(identity);
  }

  SubsetMap<int> take_inverse(int def = -1) const {
    int n = 0;
    auto it = max_element(map.begin(), map.end());
    if(it != map.end()) n = *it + 1;
    vector<int> inv(n, def);
    for(int i = 0; i < map.size(); i++)
      inv[map[i]] = i;
    return SubsetMap<int>(n, [inv](int i) -> int {
      return inv[i];
    });
  }

  void sort() const {
    std::sort(map.begin(), map.end());
  }

  Subset operator|(const Subset& rhs) const {
    sort();
    rhs.sort();
    vector<int> res;
    res.reserve(size() + rhs.size());
    merge(map.begin(), map.end(), rhs.map.begin(), rhs.map.end(), back_inserter(res));
    auto it = unique(res.begin(), res.end());
    res.resize(it - res.begin());
    return res;
  }
};

template<>
struct Map<bool> {
    std::function<bool(int)> f;
    Map() {}
    template<typename F>
    Map(const F& f_) : f(f_) {}
    bool operator()(int i) const {
      return f(i);
    }

    template <
      typename Iterator,
      typename enable_if<IsInputIterator<Iterator>::value>::type * = nullptr>
    vector<IteratorValue<Iterator>> operator()(Iterator begin, Iterator end) const {
      vector<IteratorValue<Iterator>> res;
      int i = 0;
      for(auto it = begin; it != end; ++it, ++i) {
        if(f(i)) res.push_back(*it);
      }
      return res;
    }
    template <
      typename Container,
      typename enable_if<HasInputIterator<Container>::value>::type * = nullptr>
    vector<IteratorValueOf<Container>> operator()(const Container& c) const {
      return (*this)(c.begin(), c.end());
    }

    Subset subset(int n) const {
      Subset map;
      for(int i = 0; i < n; i++)
        if(f(i)) map.add(i);
      return map;
    }

    template<typename F>
    SubsetMap<ValueType<F>> subset(int n, F && g) const {
      return subset(SubsetMap<ValueType<F>>(n, g));
    }

    template<typename T>
    SubsetMap<T> subset(const SubsetMap<T>& g) const {
      return subset(g.size()).take_from(g);
    }
};

namespace {
template<typename T,
         enable_if_t<is_same<T, bool>::value>* = nullptr>
Subset as_subset_(const SubsetMap<T>& rhs) {
  Subset map;
  for(int i = 0; i < rhs.size(); i++)
    if(rhs(i)) map.add(i);
  return map;
}
template<typename T,
         enable_if_t<!is_same<T, bool>::value>* = nullptr>
Subset as_subset_(const SubsetMap<T>& rhs) {
  Subset map;
  for(int i = 0; i < rhs.size(); i++)
    map.add(rhs(i));
  return map;
}
}


template<typename T>
Subset SubsetMap<T>::as_subset() const {
  return as_subset_(*this);
  
}

using Filter = Map<bool>;
using SubsetFilter = SubsetMap<bool>;

template<typename T>
SubsetMap<T> from_vector(const vector<T>& v) {
  return SubsetMap<T>(v.size(), [v](int i) -> T {
    return v[i];
  });
}

template<typename U, typename F, typename T = ValueType<F, U>>
SubsetMap<T> map_from_vector(const vector<U>& v, const F& f) {
  return SubsetMap<T>(v.size(), [v, f](int i) -> T {
    return f(v[i]);
  });
}

template<typename T>
SubsetFilter filter_from_vector(const vector<T>& v) {
  return SubsetFilter(v.size(), [v](int i) -> bool {
    return v[i];
  });
}

template<typename T>
SubsetFilter filter_from_sparse_vector(const vector<T>& v) {
  return SubsetFilter(v.size(), [v](int i) -> bool {
    return v[i];
  });
}
} // namespace lambda
} // namespace lib


#line 5 "matroid/v2/Matroid.cpp"

namespace lib {
  using namespace std;
struct Matroid {
  int matroid_size_;
  Matroid() {}
  Matroid(int n) : matroid_size_(n) {}
  void set_ground(int n) { matroid_size_ = n; }
  int size() const { return matroid_size_; }
  virtual int rank(const lambda::Subset&, const lambda::SubsetFilter&) = 0;
  virtual void clear() = 0;
  virtual void add(int i) = 0;
  virtual bool check(int i) = 0;

  int rank() {
    lambda::SubsetFilter f(size(), lambda::all);
    return rank(f.as_subset(), f);
  }

  vector<int> basis(const lambda::Subset& s) {
    clear();
    vector<int> res;
    for(int i : s.items()) {
      if(check(i)) {
        res.push_back(i);
        add(i);
      }
    }
    return res;
  }
  vector<int> basis() {
    return basis(lambda::Filter(lambda::all).subset(size()));
  }
};

struct IncrementalMatroid : Matroid {
  int rank(const lambda::Subset& s, const lambda::SubsetFilter&) override {
    clear();
    int ans = 0;
    for(int i : s.items())
      if(check(i)) add(i), ans++;
    return ans;
  }
};

struct RankMatroid : Matroid {
  lambda::Subset sI;
  vector<int> vI;
  void clear() override { vI.assign(size(), 0), sI.clear(); }
  void add(int i) override { vI[i] = true, sI.add(i); }
  bool check(int i) override {
    if(vI[i]) return true;
    vI[i] = true;
    sI.add(i);
    bool ok = rank(sI, lambda::filter_from_sparse_vector(vI)) >= sI.size();
    vI[i] = false;
    sI.pop();
    return ok;
  }
};

namespace matroid {
template<typename M>
using IsRank = is_base_of<RankMatroid, M>;

template<typename M>
using IsIncremental = is_base_of<IncrementalMatroid, M>;
} // namespace matroid
} // namespace lib


#line 6 "matroid/v2/EdgeFinder.cpp"

namespace lib {
  using namespace std;
namespace matroid {

template<typename M, typename F>
auto incremental_edge_finder(
  M& m,
  const lambda::Subset& sI,
  const lambda::SubsetFilter& I,
  int v,
  F && test) {
  return [&, v, test, done=0, ans=vector<int>()] () mutable {
    if(v < I.size() && !I(v)) {
      // CASE 1: v is an element not in IS.
      // In this case, should add v and remove a neighbor.
      m.clear();
      // First of all, add v.
      if(!m.check(v)) return -1;
      m.add(v);
      // Now add IS elements that aren't in B. These can't be removed.
      for(int i : sI.items()) {
        if(test(i)) continue;
        if(!m.check(i)) return -1;
        m.add(i);
      }
      // Finally, add IS elements that ARE in B. 
      for(int i : sI.items()) {
        if(!test(i)) continue;
        if(!m.check(i)) {
          // Introducing i and every element that comes next
          // makes this a circuit, that can be made independent by removing i.
          return i;
        }
        m.add(i);
      }
      // Element can be added directly, with no exchange.
      return I.size();
    }
    // CASE 2: v is source or an element in IS.
    if(!done) {
      // In this case, we should try adding elements after removing v.
      m.clear();
      for(int i : sI.items())
        if(i != v) m.add(i);
      for(int i = 0; i < I.size(); i++)
        if(!I(i) && test(i) && m.check(i))
          ans.push_back(i);
    }
    if(done < ans.size()) return ans[done++];
    return -1;
  };
}

template<typename M, typename F>
auto rank_edge_finder(
  M& m,
  const lambda::Subset& sI,
  const lambda::SubsetFilter& I,
  int v,
  F && test) {

  // Fast SubsetFilter.
  static vector<int> mask(1);
  int n = mask.size();
  while(n < I.size()) n *= 2;
  mask.assign(n, 0);

  auto filter = lambda::SubsetFilter(I.size(), [](int i) {
    return mask[i];
  });
  const static auto subset_mask = [](const lambda::Subset& s) {
    for(int i : s.items())
      mask[i] = true;
  };
  const static auto clear_mask = [](const lambda::Subset& s) {
    for(int i : s.items())
      mask[i] = false;
  };

  return [&, v, test, filter, sub=lambda::Subset()] () mutable {
    vector<int> need, extra;
    if(v < I.size() && !I(v)) {
      // CASE 1: v NOT in IS.
      // `need` will be v + elements that are in IS
      // but are not in B. Thus, they can't be part of
      // an exchange.
      // `extra` will be elements of IS that are in B.
      need.push_back(v);
      for(auto i : sI.items())
        if(!test(i)) need.push_back(i);
        else extra.push_back(i);

      auto check = [&](int mid) {
        need.insert(need.end(), extra.begin(), extra.begin() + mid);
        swap(sub.map, need);
        subset_mask(sub);
        int res = m.rank(sub, filter);
        clear_mask(sub);
        swap(sub.map, need);
        need.erase(need.end() - mid, need.end());
        return res == need.size() + mid;
      };

      // Binary search on element that makes up the circuit.
      if(!check(0)) return -1;
      if(check(extra.size())) return I.size();
      int l = 0, r = extra.size() + 1;
      while(l < r) {
        int mid = (l+r)/2;
        if(!check(mid))
          r = mid;
        else l = mid + 1;
      }
      if(l == extra.size() + 1) return I.size();
      return extra[l-1];
    }

    // CASE 2: v in IS.
    for(int i : sI.items())
      if(i != v) need.push_back(i);
    for(int i = 0; i < I.size(); i++)
      if(!I(i) && test(i)) extra.push_back(i);
    auto check = [&](int l, int r) {
      need.insert(need.end(), extra.begin() + l, extra.begin() + r);
      swap(sub.map, need);
      subset_mask(sub);
      int res = m.rank(sub, filter);
      clear_mask(sub);
      swap(sub.map, need);
      need.erase(need.end() - (r - l), need.end());
      return res > need.size();
    };

    int l = 0, r = extra.size();
    if(!check(l, r)) return -1;
    while(l < r) {
      int mid = (l+r)/2;
      if(check(l, mid+1))
        r = mid;
      else l = mid + 1;
    }
    return extra[l];
  };
}

} // namespace matroid
} // namespace lib
Back to top page