#906278 (C++17) No.2913 二次元距離空間

提出ソース
結果

問題	No.2913 二次元距離空間
ユーザー	👑 p-adic
提出日時	2023-08-19 10:29:42
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	204 ms / 2,000 ms
コード長	15,374 bytes
コンパイル時間	3,718 ms
コンパイル使用メモリ	243,532 KB
実行使用メモリ	57,164 KB
最終ジャッジ日時	2024-06-15 16:23:29
合計ジャッジ時間	6,670 ms
ジャッジサーバーID （参考情報）	judge5 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	7 ms 11,284 KB
testcase_01	AC	6 ms 11,236 KB
testcase_02	AC	6 ms 11,268 KB
testcase_03	AC	6 ms 11,336 KB
testcase_04	AC	7 ms 11,272 KB
testcase_05	AC	7 ms 11,316 KB
testcase_06	AC	6 ms 11,328 KB
testcase_07	AC	7 ms 11,108 KB
testcase_08	AC	6 ms 11,284 KB
testcase_09	AC	6 ms 11,268 KB
testcase_10	AC	8 ms 11,316 KB
testcase_11	AC	7 ms 11,196 KB
testcase_12	AC	6 ms 11,272 KB
testcase_13	AC	8 ms 11,428 KB
testcase_14	AC	6 ms 11,440 KB
testcase_15	AC	8 ms 12,232 KB
testcase_16	AC	64 ms 34,804 KB
testcase_17	AC	85 ms 34,652 KB
testcase_18	AC	174 ms 49,416 KB
testcase_19	AC	204 ms 56,280 KB
testcase_20	AC	169 ms 47,876 KB
testcase_21	AC	59 ms 38,908 KB
testcase_22	AC	53 ms 37,596 KB
testcase_23	AC	191 ms 52,932 KB
testcase_24	AC	59 ms 41,088 KB
testcase_25	AC	186 ms 53,060 KB
testcase_26	AC	55 ms 38,452 KB
testcase_27	AC	201 ms 57,164 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#ifdef DEBUG
  #define _GLIBCXX_DEBUG
  #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ); signal( SIGABRT , &AlertAbort )
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , DEBUG_VALUE )
  #define CERR( MESSAGE ) cerr << MESSAGE << endl;
  #define COUT( ANSWER ) cout << ANSWER << endl
  #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック： " << ( MIN ) << ( ( MIN ) <= A ? "<=" : ">" ) << A << ( A <= ( MAX ) ? "<=" : ">" ) << ( MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) )
#else
  #pragma GCC optimize ( "O3" )
  #pragma GCC optimize( "unroll-loops" )
  #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
  #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr )
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE )
  #define CERR( MESSAGE ) 
  #define COUT( ANSWER ) cout << ANSWER << "\n"
  #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAIN main
#define TYPE_OF( VAR ) decay_t<decltype( VAR )>
#define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE
#define CIN( LL , A ) LL A; cin >> A
#define SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX )
#define CIN_ASSERT( A , MIN , MAX ) TYPE_OF( MAX ) A; SET_ASSERT( A , MIN , MAX )
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
#define QUIT return 0
#define RETURN( ANSWER ) COUT( ( ANSWER ) ); QUIT

#ifdef DEBUG
  inline void AlertAbort( int n ) { CERR( "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); }
#endif

#define DIJKSTRA_BODY( INITIALISE_PREV , SET_PREV )			\
  static const U& unit = Unit();					\
  assert( unit != m_found && unit < m_infty );				\
  U weight[size_max];							\
									\
  for( int i = 0 ; i < m_size ; i++ ){					\
									\
    weight[i] = m_infty;						\
									\
  }									\
									\
  set<pair<U,int> > vertex{};						\
  const int i_start = e_inv( t_start );					\
  const int i_final = e_inv( t_final );					\
  vertex.insert( pair<U,int>( weight[i_start] = unit , i_start ) );	\
  INITIALISE_PREV;							\
									\
  while( ! vertex.empty() ){						\
									\
    auto itr_vertex = vertex.begin();					\
    const pair<U,int> v = *itr_vertex;					\
    const int& i = v.second;						\
									\
    if( i == i_final ){							\
									\
      break;								\
									\
    }									\
									\
    const U& u = v.first;						\
    weight[i] = m_found;						\
    vertex.erase( itr_vertex );						\
    const list<pair<T,U> > edge_i = E( e( i ) );			\
    list<pair<U,int> > changed_vertex{};				\
									\
    for( auto itr_edge_i = edge_i.begin() , end_edge_i = edge_i.end() ; itr_edge_i != end_edge_i ; itr_edge_i++ ){ \
									\
      const int& j = e_inv( itr_edge_i->first );					\
      U& weight_j = weight[j];						\
									\
      if( weight_j != m_found ){					\
									\
	const U& edge_ij = itr_edge_i->second;				\
	const U temp = Addition( u , edge_ij );				\
	assert( edge_ij != m_found && temp != m_found && !( temp < edge_ij ) && temp < m_infty ); \
									\
	if( weight_j > temp ){						\
									\
	  if( weight_j != m_infty ){					\
									\
	    vertex.erase( pair<U,int>( weight_j , j ) );		\
									\
	  }								\
									\
	  SET_PREV;							\
	  changed_vertex.push_back( pair<U,int>( weight_j = temp , j ) ); \
									\
	}								\
									\
      }									\
									\
    }									\
									\
    for( auto itr_changed = changed_vertex.begin() , end_changed = changed_vertex.end() ; itr_changed != end_changed ; itr_changed++ ){ \
									\
      vertex.insert( *itr_changed );					\
									\
    }									\
									\
  }									\

// メモリが不足する場合はEの定義を前計算しないでその都度計算させること。
template <typename T , typename U , list<pair<T,U> > E(const T&) , int size_max>
class DijkstraBody
{

private:
  int m_size;
  U m_infty;
  U m_found;

  int m_length;
  map<T,int> m_memory;
  vector<T> m_memory_inv;
  
public:
  inline DijkstraBody( const int& size , const U& infty , const U& found );
  // 経路が存在しない場合の返り値はm_infty
  U Solve( const T& t_start , const T& t_final );
  U Solve( const T& t_start , const T& t_final , list<T>& path );

  const U& Infty() const;
  
private:
  virtual const U& Unit() const = 0;
  virtual U Addition( const U& , const U& ) const = 0;
  virtual T e( const int& i );
  virtual int e_inv( const T& t );
  virtual void Reset();

};

// 入力の範囲内で要件
// (1) Eの値の各成分の第2成分が0以上である。
// (2) 2^{31}-1がEの値の各成分の第2成分size_max個以下の和で表せるいかなる数よりも大きい。
// (6) Vの各要素u,vに対し、辺u->vが複数存在する場合は重みが最小のものが前にpushされている。
// が成り立つ場合にのみサポート。

// O((size+|E|)log size)で単一始点最短経路探索。
template <list<pair<int,ll> > E(const int&) , int size_max>
class Dijkstra :
  public DijkstraBody<int,ll,E,size_max>
{

public:
  inline Dijkstra( const int& size );
  
private:
  inline const ll& Unit() const;
  inline ll Addition( const ll& , const ll& ) const;
  inline int e( const int& i );
  inline int e_inv( const int& t );
  inline void Reset();

};

// 入力の範囲内で要件
// (1) Eの値の各成分の第2成分がe_T()以上である。
// (2) inftyがEの値の各成分の第2成分size_max個以下の和で表せるいかなる項よりも大きい。
// (3) foundがEの値の各成分の第2成分size_max個以下の和で表せず、inftyとも異なる。
// (4) (U,m_U:U^2->U,e_U:1->U)がbool operator<(const U&,const U&)に関して順序モノイドである。
// (6) Vの各要素u,vに対し、辺u->vが複数存在する場合は重みが最小のものが前にpushされている。
// が成り立つ場合にのみサポート。

// O((size+|E|)(log size)^2)で単一始点最短経路探索。
template <typename T , typename U , U m_U(const U&,const U&) , const U& e_U() , list<pair<T,U> > E(const T&) , int size_max>
class MemorisationDijkstra :
  public DijkstraBody<T,U,E,size_max>
{

public:
  inline MemorisationDijkstra( const int& size , const U& infty = 9223372036854775807 , const U& found = -1 );
  
private:
  inline const U& Unit() const;
  inline U Addition( const U& , const U& ) const;

};

// 入力の範囲内で要件
// (1) Eの値の各成分の第2成分がe_T()以上である。
// (2) inftyがEの値の各成分の第2成分size_max個以下の和で表せるいかなる項よりも大きい。
// (3) foundがEの値の各成分の第2成分size_max個以下の和で表せず、inftyとも異なる。
// (4) (U,m_U:U^2->U,e_U:1->U)がbool operator<(const U&,const U&)に関して順序モノイドである。
// (5) (enum_T,enum_T_inv)が互いに逆写像である。
// (6) Vの各要素u,vに対し、辺u->vが複数存在する場合は重みが最小のものが前にpushされている。
// が成り立つ場合にのみサポート。

// O((size+|E|)log size)で単一始点最短経路探索。
template <typename T , typename U , U m_U(const U&,const U&) , const U& e_U() , list<pair<T,U> > E(const T&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)>
class EnumerationDijkstra :
  public DijkstraBody<T,U,E,size_max>
{

public:
  inline EnumerationDijkstra( const int& size , const U& infty = 9223372036854775807 , const U& found = -1 );
  
private:
  inline const U& Unit() const;
  inline U Addition( const U& , const U& ) const;
  inline T e( const int& i );
  inline int e_inv( const T& t );
  inline void Reset();

};

template <typename T , typename U , list<pair<T,U> > E(const T&) , int size_max> inline DijkstraBody<T,U,E,size_max>::DijkstraBody( const int& size , const U& infty , const U& found ) : m_size( size ) , m_infty( infty ) , m_found( found ) , m_length() , m_memory() , m_memory_inv() { static_assert( ! is_same<U,int>::value ); }
template <list<pair<int,ll> > E(const int&) , int size_max> inline Dijkstra<E,size_max>::Dijkstra( const int& size ) : DijkstraBody<int,ll,E,size_max>( size , 9223372036854775807 , -1 ) {}
template <typename T , typename U , U m_U(const U&,const U&) , const U& e_U() , list<pair<T,U> > E(const T&) , int size_max> inline MemorisationDijkstra<T,U,m_U,e_U,E,size_max>::MemorisationDijkstra( const int& size , const U& infty , const U& found ) : DijkstraBody<T,U,E,size_max>( size , infty , found ) {}
template <typename T , typename U , U m_U(const U&,const U&) , const U& e_U() , list<pair<T,U> > E(const T&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)> inline EnumerationDijkstra<T,U,m_U,e_U,E,size_max,enum_T,enum_T_inv>::EnumerationDijkstra( const int& size , const U& infty , const U& found ) : DijkstraBody<T,U,E,size_max>( size , infty , found ) {}

template <typename T , typename U , list<pair<T,U> > E(const T&) , int size_max>
U DijkstraBody<T,U,E,size_max>::Solve( const T& t_start , const T& t_final )
{

  DIJKSTRA_BODY( , );
  Reset();
  return weight[i_final];

}

template <typename T , typename U , list<pair<T,U> > E(const T&) , int size_max>
U DijkstraBody<T,U,E,size_max>::Solve( const T& t_start , const T& t_final , list<T>& path )
{

  DIJKSTRA_BODY( T prev[size_max] = {} , prev[j] = i );
  int i = i_final;

  while( i != i_start ){

    path.push_front( e( i ) );
    i = prev[i];

  }

  path.push_front( t_start );
  Reset();
  return weight[i_final];

}

template <typename T , typename U , list<pair<T,U> > E(const T&) , int size_max> const U& DijkstraBody<T,U,E,size_max>::Infty() const { return m_infty; }

template <list<pair<int,ll> > E(const int&) , int size_max> inline const ll& Dijkstra<E,size_max>::Unit() const { static const ll unit = 0; return unit; }
template <typename T , typename U , U m_U(const U&,const U&) , const U& e_U() , list<pair<T,U> > E(const T&) , int size_max> inline const U& MemorisationDijkstra<T,U,m_U,e_U,E,size_max>::Unit() const { return e_U(); }
template <typename T , typename U , U m_U(const U&,const U&) , const U& e_U() , list<pair<T,U> > E(const T&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)> inline const U& EnumerationDijkstra<T,U,m_U,e_U,E,size_max,enum_T,enum_T_inv>::Unit() const { return e_U(); }

template <list<pair<int,ll> > E(const int&) , int size_max> inline ll Dijkstra<E,size_max>::Addition( const ll& u0 , const ll& u1 ) const { return u0 + u1; }
template <typename T , typename U , U m_U(const U&,const U&) , const U& e_U() , list<pair<T,U> > E(const T&) , int size_max> inline U MemorisationDijkstra<T,U,m_U,e_U,E,size_max>::Addition( const U& u0 , const U& u1 ) const { return m_U( u0 , u1 ); }
template <typename T , typename U , U m_U(const U&,const U&) , const U& e_U() , list<pair<T,U> > E(const T&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)> inline U EnumerationDijkstra<T,U,m_U,e_U,E,size_max,enum_T,enum_T_inv>::Addition( const U& u0 , const U& u1 ) const { return m_U( u0 , u1 ); }

template <typename T , typename U , list<pair<T,U> > E(const T&) , int size_max>
T DijkstraBody<T,U,E,size_max>::e( const int& i )
{
  
  assert( i < m_length );
  return m_memory_inv[i];

}

template <list<pair<int,ll> > E(const int&) , int size_max> inline int Dijkstra<E,size_max>::e( const int& i ) { return i; }
template <typename T , typename U , U m_U(const U&,const U&) , const U& e_U() , list<pair<T,U> > E(const T&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)> inline T EnumerationDijkstra<T,U,m_U,e_U,E,size_max,enum_T,enum_T_inv>::e( const int& i ) { return enum_T( i ); }

template <typename T , typename U , list<pair<T,U> > E(const T&) , int size_max>
int DijkstraBody<T,U,E,size_max>::e_inv( const T& t )
{

  if( m_memory.count( t ) == 0 ){

    assert( m_length < m_size );
    m_memory_inv.push_back( t );
    return m_memory[t] = m_length++;

  }
  
  return m_memory[t];

}

template <list<pair<int,ll> > E(const int&) , int size_max> inline int Dijkstra<E,size_max>::e_inv( const int& t ) { return t; }
template <typename T , typename U , U m_U(const U&,const U&) , const U& e_U() , list<pair<T,U> > E(const T&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)> inline int EnumerationDijkstra<T,U,m_U,e_U,E,size_max,enum_T,enum_T_inv>::e_inv( const T& t ) { return enum_T_inv( t ); }

template <typename T , typename U , list<pair<T,U> > E(const T&) , int size_max>
void DijkstraBody<T,U,E,size_max>::Reset()
{

  m_length = 0;
  m_memory.clear();
  m_memory_inv.clear();
  return;

}

template <list<pair<int,ll> > E(const int&) , int size_max> inline void Dijkstra<E,size_max>::Reset() {}
template <typename T , typename U , U m_U(const U&,const U&) , const U& e_U() , list<pair<T,U> > E(const T&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)> inline void EnumerationDijkstra<T,U,m_U,e_U,E,size_max,enum_T,enum_T_inv>::Reset() {}

inline DEXPR( int , bound_H , 500 , 10 );
inline CEXPR( int , bound_W , bound_H );
static_assert( ll( bound_H ) * bound_W < ll( 1 ) << 31 );
inline CEXPR( int , bound_HW , bound_H * bound_W );
int H , W , H_minus , W_minus , HW;
inline pair<int,int> EnumHW( const int& v ) { return { v / W , v % W }; }
inline int EnumHW_inv( const int& h , const int& w ) { return h * W + w; }
inline void SetEdgeOnGrid( const string& Si , const int& i , list<pair<int,pair<int,int> > > ( &e )[bound_HW] , const char& walkable = '.' ){FOR(j,0,W){if(Si[j]==walkable){int v = EnumHW_inv(i,j);if(i>0){e[EnumHW_inv(i-1,j)].push_back({v,{0,1}});}if(i+1<H){e[EnumHW_inv(i+1,j)].push_back({v,{0,1}});}if(j>0){e[EnumHW_inv(i,j-1)].push_back({v,{1,0}});}if(j+1<W){e[EnumHW_inv(i,j+1)].push_back({v,{1,0}});}}else{assert(Si[j]=='#');}}}
const string direction[4] = {"U","R","D","L"};
inline int DirectionNumberOnGrid( const int& i , const int& j , const int& k , const int& h ){return i<k?2:i>k?0:j<h?1:j>h?3:(assert(false),-1);}
inline int DirectionNumberOnGrid( const int& v , const int& w ){auto [i,j]=EnumHW(v);auto [k,h]=EnumHW(w);return DirectionNumberOnGrid(i,j,k,h);}
inline int ReverseDirectionNumberOnGrid( const int& n ){assert(0<=n&&n<4);return(n+2)%4;}

list<pair<int,pair<int,int> > > e[bound_HW];
inline list<pair<int,pair<int,int> > > E( const int& v ) { return e[v]; }

inline pair<int,int> add( const pair<int,int>& t0 , const pair<int,int>& t1 ) { return { t0.first + t1.first , t0.second + t1.second }; }
inline const pair<int,int>& zero() { static const pair<int,int> z{}; return z; }
inline int id( const int& v ) { return v; }

int MAIN()
{
  UNTIE;
  SET_ASSERT( H , 2 , bound_H );
  SET_ASSERT( W , 2 , bound_W );
  H_minus = H - 1;
  W_minus = W - 1;
  HW = H * W;
  assert( HW <= bound_HW );
  FOR( i , 0 , H ){
    CIN( string , Si );
    SetEdgeOnGrid( Si , i , e );
  }
  EnumerationDijkstra<int,pair<int,int>,add,zero,E,bound_HW,id,id> dijkstra{ HW , { HW , HW } , { -1 , -1 } };
  auto [X,Y] = dijkstra.Solve( EnumHW_inv( 0 , 0 ) , EnumHW_inv( H_minus , W_minus ) );
  if( X == HW ){
    RETURN( "No" );
  }
  COUT( "Yes" );
  COUT( X << " " << Y );
  QUIT;
}
yukicoder

結果

テストケース

ソースコード
