#line 1 "grid_Dijkstra.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/20" #line 2 "/Users/akagiyasunori/Work/procon/lib/heuristic_lib/data_structures/radix_heap.hpp" #include #include #include #include #include #include #include // Radix heap for unsigned integer // https://github.com/iwiwi/radix-heap // hitonanode さんの radix heap. https://hitonanode.github.io/cplib-cpp/data_structure/radix_heap.hpp template ::value>::type * = nullptr> class radix_heap { int sz; Uint last; std::array>, std::numeric_limits::digits + 1> v; template ::type * = nullptr> static inline int bucket(U x) noexcept { return x ? 32 - __builtin_clz(x) : 0; } template ::type * = nullptr> static inline int bucket(U x) noexcept { return x ? 64 - __builtin_clzll(x) : 0; } void pull() { if (!v[0].empty()) return; int i = 1; while (v[i].empty()) ++i; last = v[i].back().first; for (int j = 0; j < int(v[i].size()); j++) last = std::min(last, v[i][j].first); for (int j = 0; j < int(v[i].size()); j++) { v[bucket(v[i][j].first ^ last)].emplace_back(std::move(v[i][j])); } v[i].clear(); } public: radix_heap() : sz(0), last(0) { static_assert(std::numeric_limits::digits > 0, "Invalid type."); } std::size_t size() const noexcept { return sz; } bool empty() const noexcept { return sz == 0; } void push(Uint x, const Label &val) { ++sz, v[bucket(x ^ last)].emplace_back(x, val); } void push(Uint x, Label &&val) { ++sz, v[bucket(x ^ last)].emplace_back(x, std::move(val)); } template void emplace(Uint x, Args &&...args) { ++sz, v[bucket(x ^ last)].emplace_back(std::piecewise_construct, std::forward_as_tuple(x), std::forward_as_tuple(args...)); } void pop() { pull(), --sz, v[0].pop_back(); } std::pair top() { return pull(), v[0].back(); } Uint top_key() { return pull(), last; } Label &top_label() { return pull(), v[0].back().second; } void clear() noexcept { sz = 0, last = 0; for (auto &vec : v) vec.clear(); } void swap(radix_heap &a) { std::swap(sz, a.sz), std::swap(last, a.last), v.swap(a.v); } }; #line 2 "/Users/akagiyasunori/Work/procon/lib/heuristic_lib/grid/grid_template.hpp" #include using namespace std; using ll = long long; template // T は辺のコストの型 struct grid_template{ const T T_INF = numeric_limits::max(); const int num_dirs = 4; const vector dx = {0, -1, 0, 1}; const vector dy = {-1, 0, 1, 0}; const vector dc = {'L', 'U', 'R', 'D'}; // H: 縦の長さ W: 横の長さ // access: 移動コストを表現する3次元配列.access[x][y][dir] はマス(x, y)から方向dirに進むときのコストを表す.-1の場合は移動不可能. int H, W; vector>> access; vector access_array; bool array_flag = false; grid_template(int H, int W): H(H), W(W){ access.resize(H); for(int i=0;i decode_grid(int x){ return {x / W, x % W}; } void make_access_array(){ for(int i=0;i> bfs(int sx, int sy){ if(!array_flag) make_access_array(); vector dist(H * W, -1); queue qu; int s = encode_grid(sx, sy); dist[s] = 0; qu.emplace(s); while(!qu.empty()){ auto v_cur = qu.front();qu.pop(); auto [cx, cy] = decode_grid(v_cur); for(int i=0;i> dist_grid(H, vector(W)); for(int i=0;i bfs_reconstruction(int sx, int sy, int tx, int ty){ if(!array_flag) make_access_array(); vector dist(H * W, -1); vector pre_v(H * W, -1); queue qu; int s = encode_grid(sx, sy); dist[s] = 0; qu.emplace(s); while(!qu.empty()){ auto v_cur = qu.front();qu.pop(); auto [cx, cy] = decode_grid(v_cur); for(int i=0;i> Dijkstra(int sx, int sy){ if(!array_flag) make_access_array(); int s = encode_grid(sx, sy); vector dist(H * W, T_INF); vector pre_v(H * W, T_INF); using Pi = pair; priority_queue, greater> pq; // radix_heap::type, int> pq; // 符号なし整数にしか使えないが,定数倍が高速 dist[s] = 0; pq.emplace(0, s); while(!pq.empty()){ auto [cost, v_cur] = pq.top();pq.pop(); auto [x_cur, y_cur] = decode_grid(v_cur); if(dist[v_cur] < cost) continue; for(int i=0;i> dist_grid(H, vector(W)); for(int i=0;i Dijkstra_reconstruction(int sx, int sy, int tx, int ty){ if(!array_flag) make_access_array(); int s = encode_grid(sx, sy); vector dist(H * W, T_INF); vector pre_v(H * W, T_INF); using Pi = pair; priority_queue, greater> pq; // radix_heap::type, int> pq; // 符号なし整数にしか使えないが,定数倍が高速 dist[s] = 0; pq.emplace(0, s); while(!pq.empty()){ auto [cost, v_cur] = pq.top();pq.pop(); auto [x_cur, y_cur] = decode_grid(v_cur); if(dist[v_cur] < cost) continue; for(int i=0;i; using pll = pair; using pdd = pair; template using V = vector; template using P = pair; template vector make_vec(size_t n, T a) { return vector(n, a); } template auto make_vec(size_t n, Ts... ts) { return vector(n, make_vec(ts...)); } template ostream& operator << (ostream& os, const pair v){os << "(" << v.first << ", " << v.second << ")"; return os;} template ostream& operator<<(ostream &os, const vector &v) { for (auto &e : v) os << e << ' '; return os; } template ostream& operator<<(ostream& os, const vector> &v){ for(auto &e : v){os << e << "\n";} return os;} struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_; template void UNIQUE(vector &x) {sort(ALL(x));x.erase(unique(ALL(x)), x.end());} template bool chmax(T &a, const T &b) { if (a bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; } void fail() { cout << -1 << '\n'; exit(0); } inline int popcount(const int x) { return __builtin_popcount(x); } inline int popcount(const ll x) { return __builtin_popcountll(x); } template void debug(vector>&v,ll h,ll w){for(ll i=0;i void debug(vector&v,ll n){if(n!=0)cerr<> N >> V >> Ox >> Oy; vector> L(N, vector(N)); for(int i=0;i> L[i][j]; } } grid_template G(N, N); for(int i=0;i= 0 and nx < N and ny >= 0 and ny < N){ G.access[i][j][k] = L[nx][ny]; } } } } auto dist1 = G.Dijkstra(0, 0); if(Ox == 0 and Oy == 0){ cout << (dist1[N-1][N-1] <= V ? "YES" : "NO") << endl; }else{ auto dist2 = G.Dijkstra(Ox-1, Oy-1); if(dist1[N-1][N-1] < V or 2 * (V - dist1[Ox-1][Oy-1]) > dist2[N-1][N-1]){ cout << "YES" << endl; }else{ cout << "NO" << endl; } } }