cp-includes

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

View the Project on GitHub rsalesc/cp-includes

:warning: matroid/MatroidIntersection.cpp

Depends on

Code

#ifndef _LIB_MATROID_INTERSECTION
#define _LIB_MATROID_INTERSECTION
#include <bits/stdc++.h>
#include "../utils/FastAdj.cpp"
#include "../utils/FastQueue.cpp"
#include "../Lambda.cpp"

namespace lib {
template<typename M1, typename M2, typename W = int>
struct MatroidIntersection {
  int n;
  M1 m1;
  M2 m2;

  // aux vectors
  vector<int> vI;
  vector<int> I;
  vector<int> nd;
  FastQueue<int> q;
  vector<int> p;
  vector<int> ch;
  vector<int> in_q;
  vector<W> w;
  vector<W> dist;

  FastAdj<int> g;

  MatroidIntersection() : q(1) { init (); }
  MatroidIntersection(int n, const M1& m1, const M2& m2) : m1(m1), m2(m2), n(n), g(n+2, n), q(n) {
    init();
  }
  void set_weights(const vector<W>& w_) {
    assert(n == w_.size());
    w = w_;
  }
  int size() const { return n; }
  void init() {
    vI.reserve(n);
    p.assign(n, -1);
    I.assign(n, false);
    nd.assign(n, 0);
  }
  void setup_augment() {
    vI.clear();
    g.clear();
    for(int i = 0; i < n; i++) {
      if(I[i]) vI.push_back(i);
      nd[i] = 0;
    }
  }
  bool is_weighted() const {
    return !w.empty();
  }
  bool augment(int truncate = 1e9) {
    setup_augment();
    if(vI.size() == min(truncate, n)) return false;
    auto f = lambda::SubsetFilter(n, [this](int i) -> bool { return in_I(i); });
    m1.build(f), m2.build(f);
    m1.setup(), m2.setup();
    // Check potential starting and ending points of the path.
    // Also, return earlier if is both starting and ending point.
    for(int i = 0; i < n; i++) {
      if(I[i]) continue;
      if(m1.can_add(i)) nd[i] |= 1;
      if(m2.can_add(i)) nd[i] |= 2;
      if(nd[i] == 3 && !is_weighted()) {
        I[i] = true;
        return true;
      }
    }
    m1.setup_graph(), m2.setup_graph();
    for(int i : vI) {
      I[i] = false;
      m1.setup_exchange(i), m2.setup_exchange(i);
      for(int j = 0; j < n; j++) {
        if(I[j] || i == j) continue;
        if(m1.can_exchange(i, j)) g.add(i, j);
        if(m2.can_exchange(i, j)) g.add(j, i);
      }
      I[i] = true;
      m1.finish_exchange(i), m2.finish_exchange(i);
    }

    int st = is_weighted() ? weighted_sp() : unweighted_sp();
    if(st == -1) return false;
    I[st] ^= 1;
    while(p[st] != st) {
      st = p[st];
      I[st] ^= 1;
    }
    return true;
  }
  int unweighted_sp() {
    q.clear();
    p.assign(n, -1);
    for(int i = 0; i < n; i++)
      if(nd[i]&1) q.push(i), p[i] = i;

    int st = -1;
    while(!q.empty() && st == -1) {
      int u = q.pop();
      if(nd[u]&2) {
        st = u;
        break;
      }
      for(int v : g.n_edges(u)) {
        if(p[v] == -1) {
          p[v] = u;
          q.push(v);
        }
      }
    }
    return st;
  }
  int weighted_sp() {
    q.clear();
    in_q.assign(n, 0);
    p.assign(n, -1);
    const W oo = numeric_limits<W>::max() / 2;
    ch.assign(n, 1e9);
    dist.assign(n, oo);
    for(int i = 0; i < n; i++)
      if(nd[i]&1)
        dist[i] = -w[i], ch[i] = 0, p[i] = i, q.push(i), in_q[i] = 1;
    while(!q.empty()) {
      int i = q.pop();
      in_q[i] = 0;
      for(int v : g.n_edges(i)) {
        if(v == i) continue;
        W n_dist = dist[i] + (I[v] ? w[v] : -w[v]);
        int n_ch = ch[i] + 1;
        using ii = pair<W, int>;
        if(ii(n_dist, n_ch) < ii(dist[v], ch[v])) {
          dist[v] = n_dist;
          ch[v] = n_ch;
          p[v] = i;
          if(!in_q[v]) {
            in_q[v] = 1;
            q.push(v);
          }
        }
      }
    }

    pair<pair<W, int>, int> best = {{oo, 1e9}, -1};
    for(int i = 0; i < n; i++) {
      if(nd[i]&2) {
        best = min(best, {{dist[i], ch[i]}, i});
      }
    }
    return best.second;
  }
  vector<int> solve(int truncate = 1e9) {
    while(augment(truncate));
    return I;
  }
  W cost() const {
    W res = 0;
    for(int i = 0; i < n; i++) {
      if(I[i])
        res += is_weighted() ? w[i] : 1;
    }
    return res;
  }
  int cardinality() const {
    int res = 0;
    for(int i = 0; i < n; i++)
      res += I[i];
    return res;
  }
  bool in_I(int i) const {
    return I[i];
  }
  void flip(int i) {
    I[i] ^= 1;
  }
  const vector<int>& get_I() const {
    return I;
  }
};

template<typename M1, typename M2>
shared_ptr<MatroidIntersection<M1, M2>> make_matroid_intersection(int n, const M1& m1, const M2& m2) {
  return make_shared<MatroidIntersection<M1, M2>>(n, m1, m2);
}
template<typename W, typename M1, typename M2>
shared_ptr<MatroidIntersection<M1, M2, W>> make_weighted_matroid_intersection(int n, const M1& m1, const M2& m2, const lambda::Map<W>& f) {
  auto res = make_shared<MatroidIntersection<M1, M2, W>>(n, m1, m2);
  vector<W> w(n);
  for(int i = 0; i < n; i++) w[i] = f(i);
  res->set_weights(w);
  return res;
}
} // namespace lib

#endif
#line 1 "matroid/MatroidIntersection.cpp"


#include <bits/stdc++.h>
#line 1 "utils/FastAdj.cpp"


#line 4 "utils/FastAdj.cpp"

namespace lib {
  using namespace std;
template<typename T>
struct FastAdj {
  int n;
  vector<T> edges;
  vector<int> head, next;
  FastAdj(int n, int cap = 0) : n(n), edges(), head(), next() {
    edges.reserve(cap);
    next.reserve(cap);
    head.assign(n, -1);
  }
  int size() const {
    return n;
  }
  int edge_size() const {
    return edges.size();
  }
  void reserve(int c) {
    edges.reserve(c);
    next.reserve(c);
  }
  void clear() {
    edges.clear();
    next.clear();
    head.assign(n, -1);
  }
  T& add(int u) {
    int K = edges.size();
    next.push_back(head[u]);
    head[u] = K;
    edges.emplace_back();
    return edges.back();
  }
  void add(int u, T v) {
    int K = edges.size();
    next.push_back(head[u]);
    head[u] = K;
    edges.push_back(v);
  }

  class iterator {
  public:
    typedef iterator self_type;
    typedef T value_type;
    typedef T &reference;
    typedef T *pointer;
    typedef std::forward_iterator_tag iterator_category;
    typedef int difference_type;
    iterator(vector<int> *next, vector<T> *edges, int ptr)
        : next_(next), edges_(edges), ptr_(ptr) {}
    self_type operator++() {
      ptr_ = (*next_)[ptr_];
      return *this;
    }
    self_type operator++(int junk) {
      self_type i = *this;
      ptr_ = (*next_)[ptr_];
      return i;
    }
    reference operator*() { return (*edges_)[ptr_]; }
    pointer operator->() { return &(*edges_)[ptr_]; }
    bool operator==(const self_type &rhs) const {
      return ptr_ == rhs.ptr_;
    }
    bool operator!=(const self_type &rhs) const { return !(*this == rhs); }

  private:
    vector<int> *next_;
    vector<T> *edges_;
    int ptr_;
  };

  class const_iterator {
  public:
    typedef const_iterator self_type;
    typedef T value_type;
    typedef T &reference;
    typedef T *pointer;
    typedef std::forward_iterator_tag iterator_category;
    typedef int difference_type;
    const_iterator(vector<int> *next, vector<T> *edges, int ptr)
        : next_(next_), edges_(edges), ptr_(ptr) {}
    self_type operator++() {
      ptr_ = (*next_)[ptr_];
      return *this;
    }
    self_type operator++(int junk) {
      self_type i = *this;
      ptr_ = (*next_)[ptr_];
      return i;
    }
    const value_type &operator*() { return (*edges_)[ptr_]; }
    const value_type *operator->() { return &(*edges_)[ptr_]; }
    bool operator==(const self_type &rhs) const {
      return ptr_ == rhs.ptr_;
    }
    bool operator!=(const self_type &rhs) const { return !(*this == rhs); }

  private:
    vector<int> *next_;
    vector<T> *edges_;
    int ptr_;
  };

  struct iterable {
    vector<int> *next_;
    vector<T> *edges_;
    int head_;

    iterable(vector<int> *next, vector<T> *edges, int head)
        : next_(next), edges_(edges), head_(head) {}

    inline iterator begin() { return iterator(next_, edges_, head_); }
    inline iterator end() { return iterator(next_, edges_, -1); }

    inline const_iterator cbegin() const {
      return const_iterator(next_, edges_, head_);
    }
    inline const_iterator cend() const {
      return const_iterator(next_, edges_, -1);
    }

    inline const_iterator begin() const { return cbegin(); }
    inline const_iterator end() const { return cend(); }
  };

  inline iterable n_edges(int i) { return iterable(&next, &edges, head[i]); }
  inline const iterable n_edges(int i) const {
    return iterable(const_cast<vector<int> *>(&next),
                    const_cast<vector<T> *>(&edges),
                    head[i]);
  }
};
} // namespace lib


#line 1 "utils/FastQueue.cpp"


#line 4 "utils/FastQueue.cpp"

namespace lib {
  using namespace std;
template<typename T>
struct FastQueue {
  vector<T> v;
  int L = 0, R = 0;
  FastQueue(int cap) : v(cap) {}

  void push(const T& no) {
    if(R >= v.size()) v.emplace_back();
    v[R++] = no;
  }
  T& front() {
    return v[L];
  }
  T front() const {
    return v[L];
  }
  T pop() {
    return v[L++];
  }
  bool empty() const {
    return L >= R;
  }
  int size() const {
    return max(R - L, 0);
  }
  void clear() {
    L = 0, R = 0;
  }
};
} // namespace lib


#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 7 "matroid/MatroidIntersection.cpp"

namespace lib {
template<typename M1, typename M2, typename W = int>
struct MatroidIntersection {
  int n;
  M1 m1;
  M2 m2;

  // aux vectors
  vector<int> vI;
  vector<int> I;
  vector<int> nd;
  FastQueue<int> q;
  vector<int> p;
  vector<int> ch;
  vector<int> in_q;
  vector<W> w;
  vector<W> dist;

  FastAdj<int> g;

  MatroidIntersection() : q(1) { init (); }
  MatroidIntersection(int n, const M1& m1, const M2& m2) : m1(m1), m2(m2), n(n), g(n+2, n), q(n) {
    init();
  }
  void set_weights(const vector<W>& w_) {
    assert(n == w_.size());
    w = w_;
  }
  int size() const { return n; }
  void init() {
    vI.reserve(n);
    p.assign(n, -1);
    I.assign(n, false);
    nd.assign(n, 0);
  }
  void setup_augment() {
    vI.clear();
    g.clear();
    for(int i = 0; i < n; i++) {
      if(I[i]) vI.push_back(i);
      nd[i] = 0;
    }
  }
  bool is_weighted() const {
    return !w.empty();
  }
  bool augment(int truncate = 1e9) {
    setup_augment();
    if(vI.size() == min(truncate, n)) return false;
    auto f = lambda::SubsetFilter(n, [this](int i) -> bool { return in_I(i); });
    m1.build(f), m2.build(f);
    m1.setup(), m2.setup();
    // Check potential starting and ending points of the path.
    // Also, return earlier if is both starting and ending point.
    for(int i = 0; i < n; i++) {
      if(I[i]) continue;
      if(m1.can_add(i)) nd[i] |= 1;
      if(m2.can_add(i)) nd[i] |= 2;
      if(nd[i] == 3 && !is_weighted()) {
        I[i] = true;
        return true;
      }
    }
    m1.setup_graph(), m2.setup_graph();
    for(int i : vI) {
      I[i] = false;
      m1.setup_exchange(i), m2.setup_exchange(i);
      for(int j = 0; j < n; j++) {
        if(I[j] || i == j) continue;
        if(m1.can_exchange(i, j)) g.add(i, j);
        if(m2.can_exchange(i, j)) g.add(j, i);
      }
      I[i] = true;
      m1.finish_exchange(i), m2.finish_exchange(i);
    }

    int st = is_weighted() ? weighted_sp() : unweighted_sp();
    if(st == -1) return false;
    I[st] ^= 1;
    while(p[st] != st) {
      st = p[st];
      I[st] ^= 1;
    }
    return true;
  }
  int unweighted_sp() {
    q.clear();
    p.assign(n, -1);
    for(int i = 0; i < n; i++)
      if(nd[i]&1) q.push(i), p[i] = i;

    int st = -1;
    while(!q.empty() && st == -1) {
      int u = q.pop();
      if(nd[u]&2) {
        st = u;
        break;
      }
      for(int v : g.n_edges(u)) {
        if(p[v] == -1) {
          p[v] = u;
          q.push(v);
        }
      }
    }
    return st;
  }
  int weighted_sp() {
    q.clear();
    in_q.assign(n, 0);
    p.assign(n, -1);
    const W oo = numeric_limits<W>::max() / 2;
    ch.assign(n, 1e9);
    dist.assign(n, oo);
    for(int i = 0; i < n; i++)
      if(nd[i]&1)
        dist[i] = -w[i], ch[i] = 0, p[i] = i, q.push(i), in_q[i] = 1;
    while(!q.empty()) {
      int i = q.pop();
      in_q[i] = 0;
      for(int v : g.n_edges(i)) {
        if(v == i) continue;
        W n_dist = dist[i] + (I[v] ? w[v] : -w[v]);
        int n_ch = ch[i] + 1;
        using ii = pair<W, int>;
        if(ii(n_dist, n_ch) < ii(dist[v], ch[v])) {
          dist[v] = n_dist;
          ch[v] = n_ch;
          p[v] = i;
          if(!in_q[v]) {
            in_q[v] = 1;
            q.push(v);
          }
        }
      }
    }

    pair<pair<W, int>, int> best = {{oo, 1e9}, -1};
    for(int i = 0; i < n; i++) {
      if(nd[i]&2) {
        best = min(best, {{dist[i], ch[i]}, i});
      }
    }
    return best.second;
  }
  vector<int> solve(int truncate = 1e9) {
    while(augment(truncate));
    return I;
  }
  W cost() const {
    W res = 0;
    for(int i = 0; i < n; i++) {
      if(I[i])
        res += is_weighted() ? w[i] : 1;
    }
    return res;
  }
  int cardinality() const {
    int res = 0;
    for(int i = 0; i < n; i++)
      res += I[i];
    return res;
  }
  bool in_I(int i) const {
    return I[i];
  }
  void flip(int i) {
    I[i] ^= 1;
  }
  const vector<int>& get_I() const {
    return I;
  }
};

template<typename M1, typename M2>
shared_ptr<MatroidIntersection<M1, M2>> make_matroid_intersection(int n, const M1& m1, const M2& m2) {
  return make_shared<MatroidIntersection<M1, M2>>(n, m1, m2);
}
template<typename W, typename M1, typename M2>
shared_ptr<MatroidIntersection<M1, M2, W>> make_weighted_matroid_intersection(int n, const M1& m1, const M2& m2, const lambda::Map<W>& f) {
  auto res = make_shared<MatroidIntersection<M1, M2, W>>(n, m1, m2);
  vector<W> w(n);
  for(int i = 0; i < n; i++) w[i] = f(i);
  res->set_weights(w);
  return res;
}
} // namespace lib
Back to top page