結果
| 問題 | No.867 避難経路 |
| ユーザー |
 fumofumofuni
|
| 提出日時 | 2023-07-01 13:03:18 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 10,112 bytes |
| コンパイル時間 | 2,030 ms |
| コンパイル使用メモリ | 213,924 KB |
| 実行使用メモリ | 271,232 KB |
| 最終ジャッジ日時 | 2024-07-07 23:37:08 |
| 合計ジャッジ時間 | 13,057 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 13 ms
16,384 KB |
| testcase_01 | AC | 15 ms
16,512 KB |
| testcase_02 | AC | 14 ms
16,512 KB |
| testcase_03 | AC | 14 ms
16,384 KB |
| testcase_04 | AC | 14 ms
16,512 KB |
| testcase_05 | AC | 15 ms
16,512 KB |
| testcase_06 | AC | 13 ms
16,512 KB |
| testcase_07 | AC | 14 ms
16,512 KB |
| testcase_08 | AC | 16 ms
16,512 KB |
| testcase_09 | AC | 14 ms
16,512 KB |
| testcase_10 | AC | 18 ms
16,512 KB |
| testcase_11 | AC | 15 ms
16,384 KB |
| testcase_12 | AC | 14 ms
16,512 KB |
| testcase_13 | AC | 15 ms
16,384 KB |
| testcase_14 | AC | 14 ms
16,512 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 | -- | - |
ソースコード
#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;
}
}
}