#886559 (C++17) No.867 避難経路

提出ソース

結果

問題	No.867 避難経路
ユーザー	fumofumofuni
提出日時	2023-07-01 13:03:18
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	10,112 bytes
コンパイル時間	2,803 ms
コンパイル使用メモリ	211,464 KB
実行使用メモリ	237,564 KB
最終ジャッジ日時	2023-09-22 07:00:23
合計ジャッジ時間	14,054 ms
ジャッジサーバーID （参考情報）	judge12 / judge14

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	16 ms 69,436 KB
testcase_01	AC	16 ms 16,384 KB
testcase_02	AC	16 ms 16,388 KB
testcase_03	AC	15 ms 16,360 KB
testcase_04	AC	16 ms 16,536 KB
testcase_05	AC	16 ms 16,388 KB
testcase_06	AC	16 ms 16,588 KB
testcase_07	AC	16 ms 16,380 KB
testcase_08	AC	15 ms 16,320 KB
testcase_09	AC	15 ms 16,536 KB
testcase_10	AC	15 ms 16,636 KB
testcase_11	AC	16 ms 16,324 KB
testcase_12	AC	16 ms 16,360 KB
testcase_13	AC	16 ms 16,460 KB
testcase_14	AC	16 ms 16,300 KB
testcase_15	TLE	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-
testcase_43	--	-

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

ソースコード

raw source code

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=(n)-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={-1,0,1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}



template<typename _Key, typename _Tp> class Fibonacci_Heap
{
public:
    using data_type = pair<_Key, _Tp>;
    class node
    {
    public:
        data_type _data;
        unsigned short int _child;
        bool _mark;
        node *_par, *_prev, *_next, *_ch_last;
        node(data_type&& data) : _data(move(data)),
            _child(0), _par(nullptr), _prev(nullptr), _next(nullptr), _ch_last(nullptr){}
        inline const _Key& get_key() const noexcept { return _data.first; }
        void insert(node *cur){
            if(_ch_last) insert_impl(cur, _ch_last);
            else _ch_last = cur, _ch_last->_prev = _ch_last->_next = _ch_last;
            ++_child, cur->_par = this;
        }
        void erase(node *cur){
            if(cur == cur->_prev){
                _ch_last = nullptr;
            }else{
                erase_impl(cur);
                if(cur == _ch_last) _ch_last = cur->_prev;
            }
            --_child, cur->_par = nullptr;
        }
    };

private:
    static constexpr float FACTOR = 1.0f / log2((1.0f + sqrt(5.0f)) / 2.0f);
    size_t _size;
    node *_minimum;
    vector<node*> rank;

    static void insert_impl(node *cur, node *next){
        cur->_prev = next->_prev, cur->_next = next;
        cur->_prev->_next = cur, next->_prev = cur;
    }
    static void erase_impl(node *cur){
        cur->_prev->_next = cur->_next, cur->_next->_prev = cur->_prev;
    }
    static int ceil2(int u){
        return 32 - __builtin_clz(u);
    }
    void root_insert(node *cur){
        if(_minimum){
            insert_impl(cur, _minimum);
            if(cur->get_key() < _minimum->get_key()) _minimum = cur;
        }else{
            _minimum = cur, _minimum->_prev = _minimum->_next = _minimum;
        }
    }
    void root_erase(node *cur){
        if(cur == cur->_prev) _minimum = nullptr;
        else erase_impl(cur);
    }
    void _delete(node *cur){
        root_erase(cur);
        delete cur;
    }
    template<typename Key, typename Data>
    node *_push(Key&& key, Data&& data){
        ++_size;
        data_type new_data(forward<Key>(key), forward<Data>(data));
        node* new_node = new node(move(new_data));
        root_insert(new_node);
        return new_node;
    }
    void _pop(){
        assert(_size > 0);
        --_size;
        if(_size == 0){
            _delete(_minimum);
            return;
        }
        if(_minimum->_ch_last){
            for(node *cur = _minimum->_ch_last->_next;;){
                node *next = cur->_next;
                _minimum->erase(cur), root_insert(cur);
                if(!_minimum->_ch_last) break;
                cur = next;
            }
        }
        unsigned int max_rank = ceil(ceil2(_size) * FACTOR);
        node *next_minimum = _minimum->_next;
        if(rank.size() <= max_rank) rank.resize(max_rank + 1);
        for(node*& cur : rank) cur = nullptr;
        for(node *cur = next_minimum; cur != _minimum;){
            if(cur->get_key() < next_minimum->get_key()) next_minimum = cur;
            node *next = cur->_next;
            unsigned int deg = cur->_child;
            while(rank[deg]){
                if(cur->get_key() < rank[deg]->get_key() || cur == next_minimum){
                    root_erase(rank[deg]), cur->insert(rank[deg]);
                }else{
                    root_erase(cur), rank[deg]->insert(cur);
                    cur = rank[deg];
                }
                rank[deg++] = nullptr;
            }
            rank[deg] = cur;
            cur = next;
        }
        _delete(_minimum);
        _minimum = next_minimum;
    }
    void _update(node *cur, const _Key& key){
        assert(!(key < (_Key)0));
        node *change = ((cur->_data.first -= key) < _minimum->get_key()) ? cur : nullptr;
        if(!cur->_par || !(cur->get_key() < cur->_par->get_key())){
            if(change) _minimum = change;
            return;
        }
        while(true){
            node *next = cur->_par;
            next->erase(cur), root_insert(cur);
            cur->_mark = false, cur = next;
            if(!cur->_par) break;
            if(!cur->_mark){
                cur->_mark = true;
                break;
            }
        }
        if(change) _minimum = change;
    }
    void clear_dfs(node *cur){
        if(cur->_ch_last){
            for(node *_cur = cur->_ch_last->_next;;){
                node *next = _cur->_next;
                if(_cur == cur->_ch_last){
                    clear_dfs(_cur);
                    break;
                }else{
                    clear_dfs(_cur);
                }
                _cur = next;
            }
        }
        delete cur;
        return;
    }
    void _clear(){
        if(!_minimum) return;
        for(node *cur = _minimum->_next;;){
            node *next = cur->_next;
            if(cur == _minimum){
                clear_dfs(cur);
                break;
            }else{
                clear_dfs(cur);
            }
            cur = next;
        }
    }

public:
    Fibonacci_Heap() noexcept : _size(0u), _minimum(nullptr){}
    Fibonacci_Heap(const Fibonacci_Heap&) = delete;
    Fibonacci_Heap(Fibonacci_Heap&& another)
        : _size(move(another._size)), rank(move(another.rank)){
        _minimum = another._minimum, another._minimum = nullptr;
    }
    Fibonacci_Heap& operator=(const Fibonacci_Heap&) = delete;
    Fibonacci_Heap& operator=(Fibonacci_Heap&& another){
        _size = move(another._size), rank = move(another.rank);
        _clear(), _minimum = another._minimum, another._minimum = nullptr;
    }
    // ~Fibonacci_Heap(){ _clear(); }
    inline bool empty() const noexcept { return (_size == 0); }
    inline size_t size() const noexcept { return _size; }
    inline const data_type& top() const noexcept { return _minimum->_data; }
    template<typename Key, typename Data>
    node *push(Key&& key, Data&& data){ return _push(forward<Key>(key), forward<Data>(data)); }
    void pop(){ _pop(); }
    void update(node *cur, const _Key& key){ _update(cur, key); }
    void clear(){ _clear(); _size = 0; rank.~vector<node*>(); }
    friend Fibonacci_Heap *unite(Fibonacci_Heap *fh1, Fibonacci_Heap *fh2){
        if(fh2->_size == 0){
            fh2->~Fibonacci_Heap();
            return fh1;
        }
        if(fh1->_size == 0){
            fh1->~Fibonacci_Heap();
            return fh2;
        }
        fh1->_minimum->_prev->_next = fh2->_minimum->_next;
        fh2->_minimum->_next->_prev = fh1->_minimum->_prev;
        fh2->_minimum->_next = fh1->_minimum;
        fh1->_minimum->_prev = fh2->_minimum;
        fh1->_size += fh2->_size;
        if(fh2->_minimum->get_key() < fh1->_minimum->get_key()) fh1->_minimum = fh2->_minimum;
        fh2->~Fibonacci_Heap();
        return fh1;
    }

    // DEBUG 用
    int dfs(node *cur, bool print, int depth) const {
        if(!cur->_ch_last){
            assert(cur->_child == 0);
            return 1;
        }
        int sz = 1;
        for(node *next = cur->_ch_last->_next; ; next = next->_next){
            if(print) cout << depth << ": " << next->_data.first << " " <<
                        next->_data.second << " " << next->_mark << endl;
            sz += dfs(next, print, depth + 1);
            if(next == cur->_ch_last) break;
        }
        return sz;
    }
    void check(bool print = false) const {
        if(!_minimum){
            assert(_size == 0);
            return;
        }
        size_t sz = 0;
        for(node *cur = _minimum->_next; ; cur = cur->_next){
            if(print) cout << "0: " << cur->_data.first << " " <<
                        cur->_data.second << endl;
            sz += dfs(cur, print, 1);
            if(cur == _minimum) break;
        }
        cout << endl;
        assert(sz == _size);
    }
};


const ll M=600;
ll dp[M][250][250];
int main(){
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  ll h,w;cin >> h >> w;
  ll x,y;cin >> x >> y;x--;y--;
  vvl g(h,vl(w));rep(i,h)rep(j,w)cin >> g[i][j];
  ll mask=1<<8;mask--;
  rep(k,M){
    rep(i,h)rep(j,w){
      dp[k][i][j]=INF;
    }
    dp[k][x][y]=g[x][y]+k*k;
    Fibonacci_Heap<ll, int> fheap;
    typename Fibonacci_Heap<ll, int>::node* keep[1<<16];
    keep[(x<<8)+y]=fheap.push(g[x][y]+k*k,(x<<8)+y);
    while(fheap.size()){
      auto [dist,v]=fheap.top();fheap.pop();
      ll nx=v>>8,ny=v&mask;
      if(dp[k][nx][ny]!=dist)continue;
      rep(i,4){
        ll nnx=nx+dx[i],nny=ny+dy[i];
        if(nnx<0||nny<0||nnx>=h||nny>=w)continue;
        ll ncost=dist+g[nnx][nny]+k*k;
        ll nto=(nnx<<8)+nny;
        if(dp[k][nnx][nny]<=ncost)continue;
        if(dp[k][nnx][nny] == INF){
            keep[nto] = fheap.push(ncost,nto);
        }else{
            fheap.update(keep[nto],  dp[k][nnx][nny]-ncost);
        }
        dp[k][nnx][nny]=ncost;
      }
    }
  }
  ll q;cin >> q;
  while(q--){
    ll nx,ny,k;cin >> nx >> ny >> k;nx--;ny--;
    if(k<M)cout << dp[k][nx][ny] << endl;
    else{
      ll f=dp[M-1][nx][ny]+(abs(nx-x)+abs(ny-y))*(k*k-(M-1)*(M-1));
      cout << f << endl;
    }
  }
}

yukicoder

結果

テストケース

ソースコード