結果

問題 No.2179 Planet Traveler
コンテスト
ユーザー 👑 p-adic
提出日時 2023-05-30 20:55:49
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 21 ms / 3,000 ms
コード長 4,815 bytes
コンパイル時間 10,688 ms
コンパイル使用メモリ 282,148 KB
最終ジャッジ日時 2025-02-13 16:52:27
ジャッジサーバーID
（参考情報） 		judge4 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #define _GLIBCXX_DEBUG
#ifndef DEBUG
  #pragma GCC optimize ( "O3" )
  #pragma GCC optimize( "unroll-loops" )
  #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::type >::type
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr )
#define CEXPR( LL , BOUND , VALUE ) constexpr const LL BOUND = VALUE
#define CIN( LL , A ) LL A; cin >> A
#define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
#define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); 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 COUT( ANSWER ) cout << ( ANSWER ) << "\n"
#define RETURN( ANSWER ) COUT( ANSWER ); QUIT

template <typename T>
class PairForDijkstra
{

private:
  T m_t;
  int m_i;

public:
  inline PairForDijkstra( const T& t = T() , const int& i = 0 );
  inline void Set( const T& t );
  inline const T& Get() const noexcept;
  inline const int& index() const noexcept;
  inline bool operator<( const PairForDijkstra& t ) const;

};

// (T,m_T:T^2->T,e_T:1->T)がbool operator<(const T&,const T&)に関して
// 順序モノイドでありdの値がe_T()以上である場合にのみサポート。
template <typename T , T m_T(const T&,const T&) , const T& e_T() , int size_max>
T Dijkstra( const T ( &d )[size_max][size_max] , const int& i_start , const int& i_final , const int& size , const T& weight_max , list<int>& path );

template <typename T> inline PairForDijkstra<T>::PairForDijkstra( const T& t , const int& i ) : m_t( t ) , m_i( i ) {}
template <typename T> inline void PairForDijkstra<T>::Set( const T& t ) { m_t = t; }
template <typename T> inline const T& PairForDijkstra<T>::Get() const noexcept { return m_t; }
template <typename T> inline const int& PairForDijkstra<T>::index() const noexcept { return m_i; }
template <typename T> inline bool PairForDijkstra<T>::operator<( const PairForDijkstra& t ) const { return m_t < t.m_t ? true : t.m_t < m_t ? false : m_i < t.m_i; }

template <typename T , T m_T(const T&,const T&) , const T& e_T() , int size_max>
T Dijkstra( const T ( &d )[size_max][size_max] , const int& i_start , const int& i_final , const int& size , const T& weight_max , list<int>& path )
{

  set<PairForDijkstra<T> > vertex{};

  for( int i = 0 ; i < size ; i++ ){

    vertex.insert( PairForDijkstra<T>( i == i_start ? e_T() : weight_max , i ) );
      
  }

  T weight[size_max] = {};
  int prev[size_max] = {};

  while( ! vertex.empty() ){

    auto itr = vertex.begin() , end = vertex.end();
    PairForDijkstra<T> v = *itr;
    const T& t = v.Get();
    const int& i = v.index();
    const T ( &di )[size_max] = d[i];
    weight[i] = t;

    if( i == i_final ){

      break;

    }

    itr = vertex.erase( itr );
    list<PairForDijkstra<T> > changed_vertex{};

    while( itr != end ){

      const T& weight_curr = itr->Get();
      const T weight_temp = m_T( t , di[itr->index()] );

      if( weight_curr > weight_temp ){

	const int i_curr = itr->index();
	prev[i_curr] = i;
	itr = vertex.erase( itr );
	changed_vertex.push_back( PairForDijkstra<T>( weight_temp , i_curr ) );

      } else {

	itr++;

      }

    }

    for( auto itr_changed = changed_vertex.begin() , end_changed = changed_vertex.end() ; itr_changed != end_changed ; itr_changed++ ){

      vertex.insert( *itr_changed );

    }
    
  }

  int i = i_final;

  while( i != i_start ){

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

  }

  path.push_front( i_start );
  return weight[ i_final ];
  
}

inline ll m( const ll& t0 , const ll& t1 ) { return max( t0 , t1 ); }
inline const ll& e() { static  const ll z{}; return z; }

int main()
{
  UNTIE;
  CEXPR( int , bound_N , 800 );
  CIN_ASSERT( N , 2 , bound_N );
  CEXPR( int , bound_XY , 20000 );
  CEXPR( int , bound_T , 1000000000 );
  static ll P[bound_N][4];
  FOR( i , 0 , N ){
    CIN_ASSERT( X , -bound_XY , bound_XY );
    CIN_ASSERT( Y , -bound_XY , bound_XY );
    CIN_ASSERT( T , 1 , bound_T );
    ll ( &Pi )[4] = P[i];
    Pi[0] = X * X + Y * Y;
    Pi[1] = X;
    Pi[2] = Y;
    Pi[3] = T;
  }
  static ll d[bound_N][bound_N];
  FOR( i , 0 , N ){
    ll ( &Pi )[4] = P[i];
    ll ( &di )[bound_N] = d[i];
    FOR( j , 0 , N ){
      ll ( &Pj )[4] = P[j];
      if( Pi[3] == Pj[3] ){
	ll X = Pj[1] - Pi[1];
	ll Y = Pj[2] - Pi[2];
	di[j] = X * X + Y * Y;
      } else {
	ll s = 4 * Pi[0] *Pj[0];
	ll r = sqrt( s ) + 1;
	while( s < r * r ){
	  r--;
	}
	di[j] = Pi[0] - r + Pj[0];
      }
    }
  }
  list<int> dummy{};
  ll answer = Dijkstra<ll,m,e,bound_N>( d , 0 , N - 1 , N , 3200000001 , dummy );
  RETURN( answer );
}
0