#794252 (C++17) No.1638 Robot Maze

提出ソース

結果

問題	No.1638 Robot Maze
ユーザー	shino16
提出日時	2022-08-31 16:34:36
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	4 ms / 2,000 ms
コード長	9,653 bytes
コンパイル時間	3,696 ms
コンパイル使用メモリ	235,576 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-11-15 02:42:28
合計ジャッジ時間	5,382 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	3 ms 6,816 KB
testcase_02	AC	3 ms 6,816 KB
testcase_03	AC	3 ms 6,816 KB
testcase_04	AC	2 ms 6,816 KB
testcase_05	AC	3 ms 6,816 KB
testcase_06	AC	2 ms 6,816 KB
testcase_07	AC	2 ms 6,816 KB
testcase_08	AC	3 ms 6,816 KB
testcase_09	AC	2 ms 6,816 KB
testcase_10	AC	2 ms 6,820 KB
testcase_11	AC	3 ms 6,820 KB
testcase_12	AC	2 ms 6,820 KB
testcase_13	AC	3 ms 6,816 KB
testcase_14	AC	3 ms 6,816 KB
testcase_15	AC	2 ms 6,816 KB
testcase_16	AC	3 ms 6,816 KB
testcase_17	AC	3 ms 6,816 KB
testcase_18	AC	3 ms 6,820 KB
testcase_19	AC	3 ms 6,820 KB
testcase_20	AC	3 ms 6,820 KB
testcase_21	AC	2 ms 6,816 KB
testcase_22	AC	3 ms 6,820 KB
testcase_23	AC	3 ms 6,820 KB
testcase_24	AC	3 ms 6,816 KB
testcase_25	AC	3 ms 6,820 KB
testcase_26	AC	2 ms 6,816 KB
testcase_27	AC	2 ms 6,820 KB
testcase_28	AC	2 ms 6,816 KB
testcase_29	AC	3 ms 6,816 KB
testcase_30	AC	3 ms 6,820 KB
testcase_31	AC	2 ms 6,816 KB
testcase_32	AC	3 ms 6,820 KB
testcase_33	AC	4 ms 6,820 KB
testcase_34	AC	4 ms 6,820 KB
testcase_35	AC	3 ms 6,816 KB
testcase_36	AC	4 ms 6,816 KB
testcase_37	AC	4 ms 6,816 KB
testcase_38	AC	4 ms 6,816 KB
testcase_39	AC	3 ms 6,820 KB
testcase_40	AC	3 ms 6,820 KB
testcase_41	AC	4 ms 6,820 KB
testcase_42	AC	3 ms 6,816 KB
testcase_43	AC	4 ms 6,816 KB
testcase_44	AC	4 ms 6,820 KB
testcase_45	AC	4 ms 6,816 KB
testcase_46	AC	4 ms 6,820 KB
testcase_47	AC	3 ms 6,816 KB
testcase_48	AC	4 ms 6,816 KB
testcase_49	AC	4 ms 6,816 KB
testcase_50	AC	4 ms 6,816 KB
testcase_51	AC	4 ms 6,816 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#line 2 "lib/prelude.hpp"
#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep2(i, m, n) for (auto i = (m); i < (n); i++)
#define rep(i, n) rep2(i, 0, n)
#define repr2(i, m, n) for (auto i = (n); i-- > (m);)
#define repr(i, n) repr2(i, 0, n)
#define all(x) begin(x), end(x)
template <class T>
auto ndvec(size_t n, T&& x) { return vector(n, forward<T>(x)); }
template <class... Ts>
auto ndvec(size_t n, Ts&&... xs) { return vector(n, forward<Ts>(xs)...); }
#line 3 "lib/graph.hpp"

struct unit_edge {
  int to;
  operator int() const { return to; }
  int w() const { return 1; }
};

template <class Weight>
struct weighted_edge {
  int to;
  Weight weight;
  operator int() const { return to; }
  Weight w() const { return weight; }
};

template <class Inner>
struct basic_graph {
  using weight_type = void;
  const Inner& inner;
  basic_graph(const Inner& g) : inner(g) {}
  template <class F>
  void adj(int v, F f) const {
    for (auto u : inner[v]) f(unit_edge{u});
  }
};

template <class Inner, class Weight>
struct basic_weighted_graph {
  using weight_type = Weight;
  const Inner& inner;
  basic_weighted_graph(const Inner& g) : inner(g) {}
  template <class F>
  void adj(int v, F f) const {
    for (auto [u, w] : inner[v]) f(weighted_edge<weight_type>{u, w});
  }
};

template <class Inner>
struct graph_trait {
  using weight_type = typename Inner::weight_type;
  const Inner& g;
  graph_trait(const Inner& g) : g(g) {}
  int size() const { return g.size(); }
  template <class F>
  void adj(int v, F f) const { g.adj(v, f); }
};

template <class T>
constexpr bool is_weighted_v =
    !is_same_v<typename graph_trait<T>::weight_type, void>;

template <class T>
using weight_t =
    conditional_t<is_weighted_v<T>, typename graph_trait<T>::weight_type, int>;

template <class T>
using edge_t =
    conditional_t<is_weighted_v<T>, weighted_edge<weight_t<T>>, unit_edge>;

template <size_t N>
struct graph_trait<vector<int>[N]> : basic_graph<vector<int>[N]> {
  using basic_graph<vector<int>[N]>::basic_graph;
  int size() const { return N; }
};

template <>
struct graph_trait<vector<vector<int>>> : basic_graph<vector<vector<int>>> {
  using basic_graph<vector<vector<int>>>::basic_graph;
  int size() const { return this->inner.size(); }
};

template <size_t N, class Weight>
struct graph_trait<vector<pair<int, Weight>>[N]>
    : basic_weighted_graph<vector<pair<int, Weight>>[N], Weight> {
      using basic_weighted_graph<vector<pair<int, Weight>>[N],
                                 Weight>::basic_weighted_graph;
      int size() const { return N; }
    };

template <class Weight>
struct graph_trait<vector<vector<pair<int, Weight>>>>
    : basic_weighted_graph<vector<vector<pair<int, Weight>>>, Weight> {
  using basic_weighted_graph<vector<vector<pair<int, Weight>>>,
                             Weight>::basic_weighted_graph;
  int size() const { return this->inner.size(); }
};
#line 3 "lib/func/constant.hpp"

template <class T, T val>
struct constant {
  template <class... Ts>
  constexpr T operator()(Ts&&...) const { return val; }
};
#line 4 "lib/graph/grid.hpp"

enum direction { Left, Right, Up, Down };

template <class Weight = constant<int, 1>, char Wall = '#'>
class grid_graph {
 public:
  template <class It>
  grid_graph(It grid, It grid_last, Weight c = Weight())
      : h(grid_last - grid + 2), w(grid[0].size() + 2), c(c),
        data(h * w, Wall) {
    rep(i, h - 2) copy(all(grid[i]), data.begin() + (i + 1) * w + 1);
  }

  int map(int r, int c) const { return (r + 1) * w + c + 1; }
  char operator[](int i) const { return data[i]; }
  char operator[](int i[2]) const { return data[map(i[0], i[1])]; }

  using weight_type = invoke_result_t<Weight, char, int>;
  int size() const { return h * w; }
  template <class F>
  void adj(int v, F f) const {
    if (data[v] == Wall) return;
    int d[] = {-1, 1, -w, w};
    rep(i, 4) if (data[v + d[i]] != Wall)
        f(edge_t<grid_graph>{v + d[i], c(data[v + d[i]], i)});
  }

 private:
  int h, w;
  Weight c;
  vector<char> data;
};
#line 3 "lib/graph/dijkstra.hpp"

template <class G, class Iter>
vector<weight_t<G>> dijkstra(const G& graph, Iter s_it, Iter s_last) {
  graph_trait<G> g(graph);
  vector<weight_t<G>> dist(g.size(), numeric_limits<weight_t<G>>::max());
  priority_queue<pair<weight_t<G>, int>, vector<pair<weight_t<G>, int>>, greater<>> hp;
  while (s_it != s_last) hp.emplace(weight_t<G>(0), *s_it), dist[*s_it++] = weight_t<G>(0);
  while (!hp.empty()) {
    auto [w, v] = hp.top();
    hp.pop();
    if (w != dist[v]) continue;
    g.adj(v, [&](auto&& e) {
      if (dist[e.to] > dist[v] + e.w())
        dist[e.to] = dist[v] + e.w(), hp.emplace(dist[e.to], e.to);
    });
  }
  return dist;
}

template <class G>
vector<weight_t<G>> dijkstra(const G& graph, int s) {
  return dijkstra(graph, &s, &s + 1);
}
#line 3 "lib/io.hpp"

template <size_t BUF_SIZE = 1 << 26>
class stdin_reader {
 public:
  stdin_reader() { buf[fread_unlocked(buf, 1, sizeof(buf), stdin)] = 0; }

  template <class T>
  enable_if_t<is_integral_v<T>> read(T& x) {
    skip(); [[maybe_unused]] bool neg = false;
    if constexpr (is_signed_v<T>) neg = *p == '-' ? (p++, true) : false;
    x = 0; while (*p > ' ') x = x * 10 + (*p++ & 0x0F);
    if constexpr (is_signed_v<T>) x = neg ? -x : x;
  }
  template <class T> void_t<decltype(&T::val)> read(T& x) { x = T((unsigned)(*this)); }
  void read(char* q) {
    skip(); char* p0 = p; while (*p > ' ') p++;
    copy(p0, p, q);
  }
  template <size_t N> void read(char (&s)[N]) { read(s); }
  void read(string& s) {
    skip(); char* p0 = p; while (*p > ' ') p++;
    s.assign(p0, p);
  }
  template <class T, class U> void read(pair<T, U>& x) { read(x.first), read(x.second); }
  template <class... Ts>
  void read(tuple<Ts...>& x) { read_tuple(x, make_index_sequence<sizeof...(Ts)>{}); }
  template <class T, size_t N> void read(T (&a)[N]) { for (auto& e : a) read(e); }

  template <class T> operator T() { T x; return read(x), x; }
  template <class... Ts> void operator()(Ts&... xs) { (read(xs), ...); }
  int operator--() { return (int)*this - 1; }
  template <class T> void vec(vector<T>& v, int n) { v.resize(n); for (auto& e : v) read(e); }
  template <class T> vector<T> vec(int n) { vector<T> v(n); return vec(v, n), v; }

 private:
  char buf[BUF_SIZE], *p = buf;
  void skip() { while (*p <= ' ') p++; }
  template <class T, size_t... Is>
  void read_tuple(T& x, index_sequence<Is...>) { (*this)(get<Is>(x)...); }
};

template <size_t BUF_SIZE = 1 << 26>
class stdout_writer {
 public:
  ~stdout_writer() { flush(); }
  void flush() { fwrite_unlocked(buf, 1, p - buf, stdout), p = buf; }
  void write_char(char c) { *p++ = c; }
  void write(char c) { write_char(c); }
  template <class T> enable_if_t<is_integral_v<T>> write(T x) {
    if (!x) return write_char('0');
    if constexpr (is_signed_v<T>) if (x < 0) write_char('-'), x = -x;
    static char tmp[16];
    char* q = end(tmp);
    while (x >= 10000) memcpy(q -= 4, four_digits.data + x % 10000 * 4, 4), x /= 10000;
    if (x < 10) write_char('0' + x);
    else if (x < 100)
      write_char('0' + (uint8_t)x / 10), write_char('0' + (uint8_t)x % 10);
    else if (x < 1000) memcpy(p, four_digits.data + x * 4 + 1, 3), p += 3;
    else memcpy(p, four_digits.data + x * 4, 4), p += 4;
    memcpy(p, q, end(tmp) - q), p += end(tmp) - q;
  }
  template <class T> void_t<decltype(&T::val)> write(T x) { write(x.val()); }
  void write(const char* s) { p = stpcpy(p, s); }
  void write(const string& s) { memcpy(p, s.c_str(), s.size()), p += s.size(); }
  template <class T, class U>
  void write(const pair<T, U>& x) { write(x.first), write_char(' '), write(x.second); }
  template <class... Ts>
  void write(const tuple<Ts...>& x) { write_tuple(x, make_index_sequence<sizeof...(Ts)>{}); }
  template <class... Ts>
  void write(const Ts&... xs) { ((write(xs), write_char(' ')), ...), --p; }
  template <class... Ts>
  void writeln(const Ts&... xs) { write(xs...), write_char('\n'); }

  template <class... Ts> void operator()(const Ts&... xs) { writeln(xs...); }
  template <class It> void iter(It first, It last) {
    while (first != last) write(*first++), write_char(' ');
    p[-1] = '\n';
  }

#define INSTANT(s) \
  void s() { writeln("s"); }
  INSTANT(No) INSTANT(NO) INSTANT(Aoki)
  INSTANT(possible) INSTANT(Possible) INSTANT(POSSIBLE)
  INSTANT(impossible) INSTANT(Impossible) INSTANT(IMPOSSIBLE)
#undef INSTANT
  void Yes(bool b = true) { writeln(b ? "Yes" : "No"); }
  void YES(bool b = true) { writeln(b ? "YES" : "NO"); }
  void Takahashi(bool b = true) { writeln(b ? "Takahashi" : "Aoki"); }

 private:
  char buf[BUF_SIZE], *p = buf;
  template <class T, size_t... Is> void write_tuple(const T& x, index_sequence<Is...>) {
    ((write(get<Is>(x)), write_char(' ')), ...), --p;
  }
  struct four_digits {
    char data[40000];
    constexpr four_digits() : data() {
      for (int i = 0; i < 10000; i++)
        for (int n = i, j = 4; j--;) data[i * 4 + j] = n % 10 + '0', n /= 10;
    }
  } static constexpr four_digits{};
};

static stdin_reader<> in;
static stdout_writer<> out;
#line 4 "main.cpp"

int main() {
  int h = in, w = in, u = in, d = in, r = in, l = in;
  ll k = in, p = in;

  int xs = --in, ys = --in, xt = --in, yt = --in;

  auto grid = in.vec<string>(h);
  auto weight = [=](char c, int dir) {
    return (c == '@' ? p : 0) + ((int[]){l, r, u, d})[dir];
  };
  grid_graph graph(all(grid), weight);
  ll ans = dijkstra(graph, graph.map(xs, ys))[graph.map(xt, yt)];
  out.Yes(ans <= k);
  (void)w;
}

yukicoder

結果

テストケース

ソースコード