結果
| 問題 | No.867 避難経路 |
| ユーザー |
 fumofumofuni
|
| 提出日時 | 2023-07-01 13:03:18 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 10,112 bytes |
| コンパイル時間 | 2,184 ms |
| コンパイル使用メモリ | 207,480 KB |
| 最終ジャッジ日時 | 2025-02-15 05:13:12 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 3 |
| other | AC * 15 TLE * 1 -- * 25 |
ソースコード
#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;}}}