Submission #409808

#	Time	Username	Problem	Language	Result	Execution time	Memory
409808		Cyanmond	Swapping Cities (APIO20_swap)	C++17	0 / 100	1 ms	204 KiB

swap

#include "bits/stdc++.h"
#ifndef CYN_LOCAL_INCLUDED
#include "swap.h"
#endif
#pragma region header
using llint = long long int;  // 64 bit
using usize = size_t;
using isie = ptrdiff_t;
template <class T>
using Vec = std::vector<T>;
template <class T, size_t N>
using Arr = std::array<T, N>;

template <class T, T Div = 2>
constexpr T infty = std::numeric_limits<T>::max() / Div;
constexpr int infi32 = infty<int, 2>;      // 1073741823
constexpr llint infi64 = infty<llint, 4>;  // 2305843009213693951
// infi32 / 2 < 10^9
// infi64 / 2 < 2 * 10^18
constexpr char endl = '\n';  // std::endl without flush ('\n')

inline int popcount(unsigned long long x) noexcept {
#if __cplusplus >= 202002L
  return std::popcount(x);  // C++20
#else
  x = x - ((x >> 1) & 0x5555555555555555);
  x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
  x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f;
  x = x + (x >> 8);
  x = x + (x >> 16);
  x = x + (x >> 32);
  return x & 0x0000007f;
#endif
}

template <class T>
constexpr bool setmin(T& a, const T b) noexcept {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
constexpr bool setmax(T& a, const T b) noexcept {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
constexpr T difrc(const T a, const T b) noexcept {
  return a > b ? a - b : b - a;
}

class range {
  using value_type = int;
  struct range_iterator {
    value_type itr;
    constexpr range_iterator(const value_type pos) noexcept : itr(pos) {}
    constexpr void operator++() noexcept { ++itr; }
    constexpr bool operator!=(const range_iterator& other) const noexcept {
      return itr != other.itr;
    }
    constexpr value_type operator*() const noexcept { return itr; }
  };
  const range_iterator first, last;

 public:
  constexpr range(const value_type first_, const value_type last_) noexcept
      : first(first_), last(last_) {}  // [l, r)
  constexpr range_iterator begin() const noexcept { return first; }
  constexpr range_iterator end() const noexcept { return last; }
};

template <class T>
class span {
  using iterator_type = typename std::vector<T>::iterator;
  iterator_type first, last;

 public:
  span(std::vector<T>& v, const usize l, const usize r) noexcept
      : first(v.begin() + l), last(v.begin() + r) {}  // [l, r)
  auto begin() const noexcept { return first; }
  auto end() const noexcept { return last; }
};

template <class F>
class rec_lambda {
  F f;

 public:
  explicit constexpr rec_lambda(F&& f_) : f(std::forward<F>(f_)) {}
  template <class... Args>
  constexpr auto operator()(Args&&... args) const {
    return f(*this, std::forward<Args>(args)...);
  }
};
#pragma endregion

class partially_persistent_UnionFind {
  std::vector<int> par, last;
  std::vector<int> edge;
  std::vector<int> deg;
  std::vector<std::vector<std::tuple<int, int, int>>> history;

 public:
  partially_persistent_UnionFind() = default;
  partially_persistent_UnionFind(int n)
      : par(n, -1), last(n, -1), history(n), edge(n, 0), deg(n, 0) {
    for (auto& vec : history) vec.emplace_back(-1, -1, 0);
  }
  void init(int n) {
    par.assign(n, -1);
    last.assign(n, -1);
    history.assign(n, std::vector<std::tuple<int, int, int>>());
    for (auto& vec : history) vec.emplace_back(-1, -1, 0);
  }
  int root(int t, int x) {
    if (last[x] == -1 || t < last[x]) return x;
    return root(t, par[x]);
  }
  bool same(int t, int x, int y) { return root(t, x) == root(t, y); }

  bool merge(int t, int x, int y) {
    ++deg[x];
    ++deg[y];
    x = root(t, x);
    y = root(t, y);
    ++edge[x];
    if (x == y) {
      history[x].emplace_back(t, par[x], edge[x]);
      return false;
    }
    if (par[x] > par[y]) std::swap(x, y);
    par[x] += par[y];
    par[y] = x;
    last[y] = t;
    edge[x] += edge[y];
    history[x].emplace_back(t, par[x], edge[x]);
    return true;
  }
  int size(int t, int x) {
    x = root(t, x);
    return -std::get<1>(*prev(lower_bound(history[x].begin(), history[x].end(),
                                          std::make_tuple(t, 0, 0))));
  }
  bool is_ok(int t, int x, int y) {
    x = root(t, x);
    y = root(t, y);
    if (x != y) return false;
    if (deg[x] > 1 or deg[y] > 1) return true;
    int a = std::get<2>(*prev(lower_bound(history[x].begin(), history[x].end(),
                                          std::make_tuple(t, 0, 0))));
    int b = size(t, x);
    return not(a == b - 1);
  }
};

namespace cs_helper {
void zip_sort_renumber([[maybe_unused]] const std::vector<usize>& order) {}
template <class T, class... Args>
void zip_sort_renumber(const std::vector<usize>& order, std::vector<T>& head,
                       Args&... args) {
  usize n = order.size();
  assert(n == head.size());
  std::vector<T> sorted_head(n);
  for (usize i = 0; i < n; ++i) sorted_head[i] = head[order[i]];
  head = std::move(sorted_head);
  zip_sort_renumber(order, args...);
}
}  // namespace cs_helper

template <class T, class... Args>
std::vector<usize> zip_sort(std::vector<T>& head, Args&... args) {
  usize n = head.size();
  std::vector<std::pair<T, usize>> tmp(n);
  for (usize i = 0; i < n; ++i) tmp[i] = std::make_pair(head[i], i);
  std::sort(tmp.begin(), tmp.end());
  std::vector<usize> order(n);
  for (usize i = 0; i < n; ++i) order[i] = tmp[i].second;
  cs_helper::zip_sort_renumber(order, head, args...);
  return order;
}

partially_persistent_UnionFind uf;
int N, M;
std::vector<int> U, V, W;

void init(int n_, int m_, std::vector<int> u_, std::vector<int> v_,
          std::vector<int> w_) {
  std::swap(N, n_);
  std::swap(M, m_);
  std::swap(U, u_);
  std::swap(V, v_);
  std::swap(W, w_);
  zip_sort(W, U, V);
  uf = partially_persistent_UnionFind(N);
  for (usize i : range(0, M)) {
    uf.merge(i, U[i], V[i]);
  }
}

int getMinimumFuelCapacity(int X, int Y) {
  int ok = M, ng = -1;
  while (ok - ng > 1) {
    const int mid = (ok + ng) >> 1;
    if (uf.is_ok(mid, X, Y))
      ok = mid;
    else
      ng = mid;
  }
  return ok == M ? -1 : W[ok];
  //
}

#ifdef CYN_LOCAL_INCLUDED
int main() {
  int n = 5, m = 6;
  std::vector<int> u = {0, 0, 1, 1, 1, 2};
  std::vector<int> v = {1, 2, 2, 3, 4, 3};
  std::vector<int> w = {4, 4, 1, 2, 10, 3};
  init(n, m, u, v, w);
  std::cout << getMinimumFuelCapacity(0, 1) << '\n';
}
#endif

Compilation message (stderr)

swap.cpp:5: warning: ignoring '#pragma region header' [-Wunknown-pragmas]
    5 | #pragma region header
      | 
swap.cpp:100: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
  100 | #pragma endregion
      | 
swap.cpp: In constructor 'partially_persistent_UnionFind::partially_persistent_UnionFind(int)':
swap.cpp:106:55: warning: 'partially_persistent_UnionFind::history' will be initialized after [-Wreorder]
  106 |   std::vector<std::vector<std::tuple<int, int, int>>> history;
      |                                                       ^~~~~~~
swap.cpp:104:20: warning:   'std::vector<int> partially_persistent_UnionFind::edge' [-Wreorder]
  104 |   std::vector<int> edge;
      |                    ^~~~
swap.cpp:110:3: warning:   when initialized here [-Wreorder]
  110 |   partially_persistent_UnionFind(int n)
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27