Submission #825719

#	Time	Username	Problem	Language	Result	Execution time	Memory
825719		KoD	Cyberland (APIO23_cyberland)	C++17	Compilation error	0 ms	0 KiB

cyberland

#include "cyberland.h"

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <variant>

namespace kod {
namespace util {

template <class F> class FixedPoint : private F {
    constexpr FixedPoint(F&& f) noexcept : F(std::forward<F>(f)) {}
    template <class G> friend constexpr decltype(auto) make_fixed(G&&) noexcept;

  public:
    template <class... Args> constexpr decltype(auto) operator()(Args&&... args) const noexcept {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

template <class G> [[nodiscard]] constexpr decltype(auto) make_fixed(G&& g) noexcept {
    using F = std::decay_t<G>;
    return FixedPoint<F>(std::forward<F>(g));
}

}  // namespace util
}  // namespace kod

namespace kod {
namespace util {

class ForwardLoop {
    int x, y;
    constexpr ForwardLoop(int x, int y) noexcept : x(x), y(y) {}
    friend constexpr ForwardLoop rep(int, int) noexcept;
    friend constexpr ForwardLoop rep(int) noexcept;

  public:
    constexpr ForwardLoop begin() const noexcept { return *this; }
    constexpr std::monostate end() const noexcept { return {}; }
    constexpr bool operator!=(std::monostate) const noexcept { return x < y; }
    constexpr void operator++() const noexcept {}
    constexpr int operator*() noexcept { return x++; }
};

[[nodiscard]] constexpr ForwardLoop rep(int l, int r) noexcept { return ForwardLoop(l, r); }
[[nodiscard]] constexpr ForwardLoop rep(int n) noexcept { return ForwardLoop(0, n); }

class BackwardLoop {
    int x, y;
    constexpr BackwardLoop(int x, int y) noexcept : x(x), y(y) {}
    friend constexpr BackwardLoop revrep(int, int) noexcept;
    friend constexpr BackwardLoop revrep(int) noexcept;

  public:
    constexpr BackwardLoop begin() const noexcept { return *this; }
    constexpr std::monostate end() const noexcept { return {}; }
    constexpr bool operator!=(std::monostate) const noexcept { return x > y; }
    constexpr void operator++() const noexcept {}
    constexpr int operator*() noexcept { return --x; }
};

[[nodiscard]] constexpr BackwardLoop revrep(int l, int r) noexcept { return BackwardLoop(r, l); }
[[nodiscard]] constexpr BackwardLoop revrep(int n) noexcept { return BackwardLoop(n, 0); }

template <class F> constexpr void repeat(int n, const F& f) noexcept {
    assert(n >= 0);
    while (n--) f();
}

}  // namespace util
}  // namespace kod

namespace kod {
namespace sol {

using ll = long long;
using uint = unsigned;
using ull = unsigned long long;

using std::array;
using std::pair;
using std::string;
using std::tuple;
using std::vector;

using namespace util;

constexpr int inf = std::numeric_limits<int>::max() / 2;
constexpr ll infll = std::numeric_limits<ll>::max() / 2;

constexpr ll floor_div(ll x, ll y) noexcept {
    assert(y != 0);
    return x / y - ((x ^ y) < 0 && x % y != 0);
}
constexpr ll ceil_div(ll x, ll y) noexcept {
    assert(y != 0);
    return x / y + ((x ^ y) >= 0 && x % y != 0);
}

template <class T> constexpr bool setmin(T& lhs, const T& rhs) noexcept {
    if (lhs > rhs) {
        lhs = rhs;
        return true;
    }
    return false;
}
template <class T> constexpr bool setmax(T& lhs, const T& rhs) noexcept {
    if (lhs < rhs) {
        lhs = rhs;
        return true;
    }
    return false;
}

}  // namespace sol
}  // namespace kod

#ifdef KOD_LOCAL
#define OJ_LOCAL(a, b) b
#include <kodlib/misc/debug>
#else
#define OJ_LOCAL(a, b) a
#define DBG(...)
#define SHOW(...)
#endif

constexpr int T = 67;
std::array<double, T> dist[100000];

template <class T> class SimpleQueue {
    std::vector<T> payload;
    int pos;

  public:
    SimpleQueue() : payload(), pos(0) {}
    explicit SimpleQueue(const int n) : SimpleQueue() { reserve(n); }

    int size() const { return (int)payload.size() - pos; }
    bool empty() const { return size() == 0; }
    T& front() { return payload[pos]; }

    void push(const T& t) { payload.push_back(t); }
    void push(T&& t) { payload.push_back(std::move(t)); }
    void pop() { pos++; }

    void reserve(int n) { payload.reserve(n); }
    void clear() {
        payload.clear();
        pos = 0;
    }
};

double solve(int N,
             int M,
             int K,
             int H,
             std::vector<int> X,
             std::vector<int> Y,
             std::vector<int> C,
             std::vector<int> A) {
    using namespace kod::sol;

    vector<int> deg(N + 1);
    for (const int i : rep(M)) {
        deg[X[i]] += 1;
        deg[Y[i]] += 1;
    }
    for (const int i : rep(N)) {
        deg[i + 1] += deg[i];
    }
    vector<int> graph(2 * M);
    for (const int i : rep(M)) {
        graph[--deg[X[i]]] = i;
        graph[--deg[Y[i]]] = i;
    }

    vector<char> reach(N);
    {
        SimpleQueue<int> que(N);
        const auto push = [&](int u) {
            if (!reach[u]) {
                reach[u] = true;
                que.push(u);
            }
        };
        push(0);
        while (!que.empty()) {
            const int u = que.front();
            que.pop();
            if (u == H) continue;
            for (const int i : rep(deg[u], deg[u + 1])) {
                const int e = graph[i];
                const int v = X[e] ^ Y[e] ^ u;
                push(v);
            }
        }
    }

    if (!reach[H]) {
        return -1;
    }

    for (const int i : rep(N)) {
        dist[i].fill(infll);
    }
    struct info {
        int u, k;
        double d;
        bool operator<(const info& t) const { return d > t.d; }
    };
    std::priority_queue<info> heap;
    const auto push = [&](int u, int k, double d) {
        if (k < std::min(K + 1, T) && setmin(dist[u][k], d)) {
            heap.push({u, k, d});
        }
    };

    push(0, 0, 0);
    for (const int i : rep(N)) {
        if (reach[i] && A[i] == 0) {
            push(i, 0, 0);
        }
    }
    while (!heap.empty()) {
        const auto [u, k, d] = heap.top();
        heap.pop();
        if (u == H) continue;
        if (d > dist[u][k] + 1e-9) continue;
        for (const int i : rep(deg[u], deg[u + 1])) {
            const int e = graph[i];
            const int v = X[e] ^ Y[e] ^ u;
            push(v, k, d + C[e]);
            if (A[v] == 2) {
                push(v, k + 1, (d + C[e]) / 2);
            }
        }
    }

    return *std::min_element(dist[H].begin(), dist[H].end());
}
#include <vector>

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr);
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <variant>

namespace kod {
namespace util {

template <class F> class FixedPoint : private F {
  constexpr FixedPoint(F&& f) noexcept : F(std::forward<F>(f)) {}
  template <class G> friend constexpr decltype(auto) make_fixed(G&&) noexcept;

 public:
  template <class... Args> constexpr decltype(auto) operator()(Args&&... args) const noexcept {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};

template <class G> [[nodiscard]] constexpr decltype(auto) make_fixed(G&& g) noexcept {
  using F = std::decay_t<G>;
  return FixedPoint<F>(std::forward<F>(g));
}

}  // namespace util
}  // namespace kod

namespace kod {
namespace util {

class ForwardLoop {
  int x, y;
  constexpr ForwardLoop(int x, int y) noexcept : x(x), y(y) {}
  friend constexpr ForwardLoop rep(int, int) noexcept;
  friend constexpr ForwardLoop rep(int) noexcept;

 public:
  constexpr ForwardLoop begin() const noexcept { return *this; }
  constexpr std::monostate end() const noexcept { return {}; }
  constexpr bool operator!=(std::monostate) const noexcept { return x < y; }
  constexpr void operator++() const noexcept {}
  constexpr int operator*() noexcept { return x++; }
};

[[nodiscard]] constexpr ForwardLoop rep(int l, int r) noexcept { return ForwardLoop(l, r); }
[[nodiscard]] constexpr ForwardLoop rep(int n) noexcept { return ForwardLoop(0, n); }

class BackwardLoop {
  int x, y;
  constexpr BackwardLoop(int x, int y) noexcept : x(x), y(y) {}
  friend constexpr BackwardLoop revrep(int, int) noexcept;
  friend constexpr BackwardLoop revrep(int) noexcept;

 public:
  constexpr BackwardLoop begin() const noexcept { return *this; }
  constexpr std::monostate end() const noexcept { return {}; }
  constexpr bool operator!=(std::monostate) const noexcept { return x > y; }
  constexpr void operator++() const noexcept {}
  constexpr int operator*() noexcept { return --x; }
};

[[nodiscard]] constexpr BackwardLoop revrep(int l, int r) noexcept { return BackwardLoop(r, l); }
[[nodiscard]] constexpr BackwardLoop revrep(int n) noexcept { return BackwardLoop(n, 0); }

template <class F> constexpr void repeat(int n, const F& f) noexcept {
  assert(n >= 0);
  while (n--) f();
}

}  // namespace util
}  // namespace kod

namespace kod {
namespace sol {

using ll = long long;
using uint = unsigned;
using ull = unsigned long long;

using std::array;
using std::pair;
using std::string;
using std::tuple;
using std::vector;

using namespace util;

constexpr int inf = std::numeric_limits<int>::max() / 2;
constexpr ll infll = std::numeric_limits<ll>::max() / 2;

constexpr ll floor_div(ll x, ll y) noexcept {
  assert(y != 0);
  return x / y - ((x ^ y) < 0 && x % y != 0);
}
constexpr ll ceil_div(ll x, ll y) noexcept {
  assert(y != 0);
  return x / y + ((x ^ y) >= 0 && x % y != 0);
}

template <class T> constexpr bool setmin(T& lhs, const T& rhs) noexcept {
  if (lhs > rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}
template <class T> constexpr bool setmax(T& lhs, const T& rhs) noexcept {
  if (lhs < rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}

}  // namespace sol
}  // namespace kod

#ifdef KOD_LOCAL
#define OJ_LOCAL(a, b) b
#include <kodlib/misc/debug>
#else
#define OJ_LOCAL(a, b) a
#define DBG(...)
#define SHOW(...)
#endif

double solve(int N, int M, int K, int H, std::vector<int> X, std::vector<int> Y, std::vector<int> C, std::vector<int> A) {
  using namespace kod::sol;

  vector<vector<int>> graph(N);
  for (const int i : rep(M)) {
    graph[X[i]].push_back(i);
    graph[Y[i]].push_back(i);
  }

  vector<char> reach(N);
  {
    std::queue<int> que;
    const auto push = [&](int u) {
      if (!reach[u]) {
        reach[u] = true;
        que.push(u);
      }
    };
    push(0);
    while (!que.empty()) {
      const int u = que.front();
      que.pop();
      if (u == H) continue;
      for (const int e : graph[u]) {
        const int v = X[e] ^ Y[e] ^ u;
        push(v);
      }
    }
  }

  if (!reach[H]) {
    return -1;
  }

  constexpr int T = 70;
  vector<array<double, T>> dist(N);
  for (auto& a : dist) a.fill(infll);

  struct info {
    int u, k;
    double d;
    bool operator<(const info& t) const { return d > t.d; }
  };
  std::priority_queue<info> heap;
  const auto push = [&](int u, int k, double d) {
    if (k < std::min(K + 1, T) && setmin(dist[u][k], d)) {
      heap.push({u, k, d});
    }
  };

  push(0, 0, 0);
  for (const int i : rep(N)) {
    if (reach[i] && A[i] == 0) {
      push(i, 0, 0);
    }
  }
  while (!heap.empty()) {
    const auto [u, k, d] = heap.top();
    heap.pop();
    if (u == H) continue;
    if (d > dist[u][k] + 1e-6) continue;
    for (const int e : graph[u]) {
      const int v = X[e] ^ Y[e] ^ u;
      push(v, k, d + C[e]);
      if (A[v] == 2) {
        push(v, k + 1, (d + C[e]) / 2);
      }
    }
  }

  return *std::min_element(dist[H].begin(), dist[H].end());
}

Compilation message (stderr)

cyberland.cpp:299:26: error: redefinition of 'class kod::util::FixedPoint<F>'
  299 | template <class F> class FixedPoint : private F {
      |                          ^~~~~~~~~~
cyberland.cpp:34:26: note: previous definition of 'class kod::util::FixedPoint<F>'
   34 | template <class F> class FixedPoint : private F {
      |                          ^~~~~~~~~~
cyberland.cpp:309:59: error: redefinition of 'template<class G> constexpr decltype(auto) kod::util::make_fixed(G&&)'
  309 | template <class G> [[nodiscard]] constexpr decltype(auto) make_fixed(G&& g) noexcept {
      |                                                           ^~~~~~~~~~
cyberland.cpp:44:59: note: 'template<class G> constexpr decltype(auto) kod::util::make_fixed(G&&)' previously declared here
   44 | template <class G> [[nodiscard]] constexpr decltype(auto) make_fixed(G&& g) noexcept {
      |                                                           ^~~~~~~~~~
cyberland.cpp:320:7: error: redefinition of 'class kod::util::ForwardLoop'
  320 | class ForwardLoop {
      |       ^~~~~~~~~~~
cyberland.cpp:55:7: note: previous definition of 'class kod::util::ForwardLoop'
   55 | class ForwardLoop {
      |       ^~~~~~~~~~~
cyberland.cpp:334:37: error: redefinition of 'constexpr kod::util::ForwardLoop kod::util::rep(int, int)'
  334 | [[nodiscard]] constexpr ForwardLoop rep(int l, int r) noexcept { return ForwardLoop(l, r); }
      |                                     ^~~
cyberland.cpp:69:37: note: 'constexpr kod::util::ForwardLoop kod::util::rep(int, int)' previously defined here
   69 | [[nodiscard]] constexpr ForwardLoop rep(int l, int r) noexcept { return ForwardLoop(l, r); }
      |                                     ^~~
cyberland.cpp: In function 'constexpr kod::util::ForwardLoop kod::util::rep(int, int)':
cyberland.cpp:334:89: error: 'constexpr kod::util::ForwardLoop::ForwardLoop(int, int)' is private within this context
  334 | [[nodiscard]] constexpr ForwardLoop rep(int l, int r) noexcept { return ForwardLoop(l, r); }
      |                                                                                         ^
cyberland.cpp:57:15: note: declared private here
   57 |     constexpr ForwardLoop(int x, int y) noexcept : x(x), y(y) {}
      |               ^~~~~~~~~~~
cyberland.cpp: At global scope:
cyberland.cpp:335:37: error: redefinition of 'constexpr kod::util::ForwardLoop kod::util::rep(int)'
  335 | [[nodiscard]] constexpr ForwardLoop rep(int n) noexcept { return ForwardLoop(0, n); }
      |                                     ^~~
cyberland.cpp:70:37: note: 'constexpr kod::util::ForwardLoop kod::util::rep(int)' previously defined here
   70 | [[nodiscard]] constexpr ForwardLoop rep(int n) noexcept { return ForwardLoop(0, n); }
      |                                     ^~~
cyberland.cpp: In function 'constexpr kod::util::ForwardLoop kod::util::rep(int)':
cyberland.cpp:335:82: error: 'constexpr kod::util::ForwardLoop::ForwardLoop(int, int)' is private within this context
  335 | [[nodiscard]] constexpr ForwardLoop rep(int n) noexcept { return ForwardLoop(0, n); }
      |                                                                                  ^
cyberland.cpp:57:15: note: declared private here
   57 |     constexpr ForwardLoop(int x, int y) noexcept : x(x), y(y) {}
      |               ^~~~~~~~~~~
cyberland.cpp: At global scope:
cyberland.cpp:337:7: error: redefinition of 'class kod::util::BackwardLoop'
  337 | class BackwardLoop {
      |       ^~~~~~~~~~~~
cyberland.cpp:72:7: note: previous definition of 'class kod::util::BackwardLoop'
   72 | class BackwardLoop {
      |       ^~~~~~~~~~~~
cyberland.cpp:351:38: error: redefinition of 'constexpr kod::util::BackwardLoop kod::util::revrep(int, int)'
  351 | [[nodiscard]] constexpr BackwardLoop revrep(int l, int r) noexcept { return BackwardLoop(r, l); }
      |                                      ^~~~~~
cyberland.cpp:86:38: note: 'constexpr kod::util::BackwardLoop kod::util::revrep(int, int)' previously defined here
   86 | [[nodiscard]] constexpr BackwardLoop revrep(int l, int r) noexcept { return BackwardLoop(r, l); }
      |                                      ^~~~~~
cyberland.cpp: In function 'constexpr kod::util::BackwardLoop kod::util::revrep(int, int)':
cyberland.cpp:351:94: error: 'constexpr kod::util::BackwardLoop::BackwardLoop(int, int)' is private within this context
  351 | [[nodiscard]] constexpr BackwardLoop revrep(int l, int r) noexcept { return BackwardLoop(r, l); }
      |                                                                                              ^
cyberland.cpp:74:15: note: declared private here
   74 |     constexpr BackwardLoop(int x, int y) noexcept : x(x), y(y) {}
      |               ^~~~~~~~~~~~
cyberland.cpp: At global scope:
cyberland.cpp:352:38: error: redefinition of 'constexpr kod::util::BackwardLoop kod::util::revrep(int)'
  352 | [[nodiscard]] constexpr BackwardLoop revrep(int n) noexcept { return BackwardLoop(n, 0); }
      |                                      ^~~~~~
cyberland.cpp:87:38: note: 'constexpr kod::util::BackwardLoop kod::util::revrep(int)' previously defined here
   87 | [[nodiscard]] constexpr BackwardLoop revrep(int n) noexcept { return BackwardLoop(n, 0); }
      |                                      ^~~~~~
cyberland.cpp: In function 'constexpr kod::util::BackwardLoop kod::util::revrep(int)':
cyberland.cpp:352:87: error: 'constexpr kod::util::BackwardLoop::BackwardLoop(int, int)' is private within this context
  352 | [[nodiscard]] constexpr BackwardLoop revrep(int n) noexcept { return BackwardLoop(n, 0); }
      |                                                                                       ^
cyberland.cpp:74:15: note: declared private here
   74 |     constexpr BackwardLoop(int x, int y) noexcept : x(x), y(y) {}
      |               ^~~~~~~~~~~~
cyberland.cpp: At global scope:
cyberland.cpp:354:35: error: redefinition of 'template<class F> constexpr void kod::util::repeat(int, const F&)'
  354 | template <class F> constexpr void repeat(int n, const F& f) noexcept {
      |                                   ^~~~~~
cyberland.cpp:89:35: note: 'template<class F> constexpr void kod::util::repeat(int, const F&)' previously declared here
   89 | template <class F> constexpr void repeat(int n, const F& f) noexcept {
      |                                   ^~~~~~
cyberland.cpp:377:15: error: redefinition of 'constexpr const int kod::sol::inf'
  377 | constexpr int inf = std::numeric_limits<int>::max() / 2;
      |               ^~~
cyberland.cpp:112:15: note: 'constexpr const int kod::sol::inf' previously defined here
  112 | constexpr int inf = std::numeric_limits<int>::max() / 2;
      |               ^~~
cyberland.cpp:378:14: error: redefinition of 'constexpr const ll kod::sol::infll'
  378 | constexpr ll infll = std::numeric_limits<ll>::max() / 2;
      |              ^~~~~
cyberland.cpp:113:14: note: 'constexpr const ll kod::sol::infll' previously defined here
  113 | constexpr ll infll = std::numeric_limits<ll>::max() / 2;
      |              ^~~~~
cyberland.cpp:380:14: error: redefinition of 'constexpr kod::sol::ll kod::sol::floor_div(kod::sol::ll, kod::sol::ll)'
  380 | constexpr ll floor_div(ll x, ll y) noexcept {
      |              ^~~~~~~~~
cyberland.cpp:115:14: note: 'constexpr kod::sol::ll kod::sol::floor_div(kod::sol::ll, kod::sol::ll)' previously defined here
  115 | constexpr ll floor_div(ll x, ll y) noexcept {
      |              ^~~~~~~~~
cyberland.cpp:384:14: error: redefinition of 'constexpr kod::sol::ll kod::sol::ceil_div(kod::sol::ll, kod::sol::ll)'
  384 | constexpr ll ceil_div(ll x, ll y) noexcept {
      |              ^~~~~~~~
cyberland.cpp:119:14: note: 'constexpr kod::sol::ll kod::sol::ceil_div(kod::sol::ll, kod::sol::ll)' previously defined here
  119 | constexpr ll ceil_div(ll x, ll y) noexcept {
      |              ^~~~~~~~
cyberland.cpp:389:35: error: redefinition of 'template<class T> constexpr bool kod::sol::setmin(T&, const T&)'
  389 | template <class T> constexpr bool setmin(T& lhs, const T& rhs) noexcept {
      |                                   ^~~~~~
cyberland.cpp:124:35: note: 'template<class T> constexpr bool kod::sol::setmin(T&, const T&)' previously declared here
  124 | template <class T> constexpr bool setmin(T& lhs, const T& rhs) noexcept {
      |                                   ^~~~~~
cyberland.cpp:396:35: error: redefinition of 'template<class T> constexpr bool kod::sol::setmax(T&, const T&)'
  396 | template <class T> constexpr bool setmax(T& lhs, const T& rhs) noexcept {
      |                                   ^~~~~~
cyberland.cpp:131:35: note: 'template<class T> constexpr bool kod::sol::setmax(T&, const T&)' previously declared here
  131 | template <class T> constexpr bool setmax(T& lhs, const T& rhs) noexcept {
      |                                   ^~~~~~
cyberland.cpp:416:8: error: redefinition of 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)'
  416 | double solve(int N, int M, int K, int H, std::vector<int> X, std::vector<int> Y, std::vector<int> C, std::vector<int> A) {
      |        ^~~~~
cyberland.cpp:177:8: note: 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)' previously defined here
  177 | double solve(int N,
      |        ^~~~~