結果

問題 No.2916 累進コスト最小化
ユーザー 👑 p-adicp-adic
提出日時 2023-10-21 10:00:29
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 357 ms / 3,500 ms
コード長 15,575 bytes
コンパイル時間 3,100 ms
コンパイル使用メモリ 236,784 KB
実行使用メモリ 25,732 KB
最終ジャッジ日時 2024-10-05 01:05:43
合計ジャッジ時間 7,285 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 357 ms
25,724 KB
testcase_01 AC 3 ms
8,404 KB
testcase_02 AC 4 ms
8,228 KB
testcase_03 AC 3 ms
8,180 KB
testcase_04 AC 4 ms
8,296 KB
testcase_05 AC 3 ms
8,232 KB
testcase_06 AC 3 ms
8,068 KB
testcase_07 AC 4 ms
8,232 KB
testcase_08 AC 3 ms
8,368 KB
testcase_09 AC 4 ms
8,228 KB
testcase_10 AC 3 ms
8,360 KB
testcase_11 AC 3 ms
8,308 KB
testcase_12 AC 4 ms
8,188 KB
testcase_13 AC 3 ms
8,324 KB
testcase_14 AC 4 ms
8,348 KB
testcase_15 AC 3 ms
8,212 KB
testcase_16 AC 2 ms
8,408 KB
testcase_17 AC 3 ms
8,224 KB
testcase_18 AC 2 ms
8,360 KB
testcase_19 AC 3 ms
8,188 KB
testcase_20 AC 3 ms
8,364 KB
testcase_21 AC 3 ms
8,220 KB
testcase_22 AC 4 ms
8,352 KB
testcase_23 AC 4 ms
8,232 KB
testcase_24 AC 47 ms
19,924 KB
testcase_25 AC 69 ms
19,772 KB
testcase_26 AC 276 ms
23,292 KB
testcase_27 AC 293 ms
23,728 KB
testcase_28 AC 256 ms
21,796 KB
testcase_29 AC 301 ms
23,744 KB
testcase_30 AC 182 ms
17,172 KB
testcase_31 AC 245 ms
20,636 KB
testcase_32 AC 342 ms
25,712 KB
testcase_33 AC 356 ms
25,732 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef DEBUG
  #define _GLIBCXX_DEBUG
  #define SIGNAL signal( SIGABRT , &AlertAbort );
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , DEBUG_VALUE )
  #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック： " , ( MIN ) , ( ( MIN ) <= A ? "<=" : ">" ) , A , ( A <= ( MAX ) ? "<=" : ">" ) , ( MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) )
  #define CERR( ... ) VariadicCout( cerr , __VA_ARGS__ ) << endl
  #define COUT( ... ) VariadicCout( cout << "出力： " , __VA_ARGS__ ) << endl
  #define CERR_A( A , N ) OUTPUT_ARRAY( cerr , A , N ) << endl
  #define COUT_A( A , N ) cout << "出力： "; OUTPUT_ARRAY( cout , A , N ) << endl
  #define CERR_ITR( A ) OUTPUT_ITR( cerr , A ) << endl
  #define COUT_ITR( A ) cout << "出力： "; OUTPUT_ITR( cout , A ) << endl
#else
  #pragma GCC optimize ( "O3" )
  #pragma GCC optimize ( "unroll-loops" )
  #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
  #define SIGNAL 
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE )
  #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
  #define CERR( ... ) 
  #define COUT( ... ) VariadicCout( cout , __VA_ARGS__ ) << "\n"
  #define CERR_A( A , N ) 
  #define COUT_A( A , N ) OUTPUT_ARRAY( cout , A , N ) << "\n"
  #define CERR_ITR( A ) 
  #define COUT_ITR( A ) OUTPUT_ITR( cout , A ) << "\n"
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
template <typename INT> using T2 = pair<INT,INT>;
#define REPEAT_MAIN( BOUND ) int main(){ ios_base::sync_with_stdio( false ); cin.tie( nullptr ); SIGNAL; DEXPR( int , bound_test_case_num , BOUND , min( BOUND , 100 ) ); int test_case_num = 1; if constexpr( bound_test_case_num > 1 ){ SET_ASSERT( test_case_num , 1 , bound_test_case_num ); } REPEAT( test_case_num ){ if constexpr( bound_test_case_num > 1 ){ CERR( "testcase " , VARIABLE_FOR_REPEAT_test_case_num , ":" ); } Solve(); CERR( "" ); } }
#define TYPE_OF( VAR ) decay_t<decltype( VAR )>
#define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE
#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 FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ )
#define FOREQINV( VAR , INITIAL , FINAL ) for( TYPE_OF( INITIAL ) VAR = INITIAL ; VAR >= FINAL ; VAR -- )
#define AUTO_ITR( ARRAY ) auto itr_ ## ARRAY = ARRAY .begin() , end_ ## ARRAY = ARRAY .end()
#define FOR_ITR( ARRAY ) for( AUTO_ITR( ARRAY ) , itr = itr_ ## ARRAY ; itr_ ## ARRAY != end_ ## ARRAY ; itr_ ## ARRAY ++ , itr++ )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT_ ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES )
#define OUTPUT_ARRAY( OS , A , N ) FOR( VARIABLE_FOR_OUTPUT_ARRAY , 0 , N ){ OS << A[VARIABLE_FOR_OUTPUT_ARRAY] << (VARIABLE_FOR_OUTPUT_ARRAY==N-1?"":" "); } OS
#define OUTPUT_ITR( OS , A ) { auto ITERATOR_FOR_OUTPUT_ITR = A.begin() , END_FOR_OUTPUT_ITR = A.end(); bool VARIABLE_FOR_OUTPUT_ITR = ITERATOR_FOR_COUT_ITR != END_FOR_COUT_ITR; while( VARIABLE_FOR_OUTPUT_ITR ){ OS << *ITERATOR_FOR_COUT_ITR; ( VARIABLE_FOR_OUTPUT_ITR = ++ITERATOR_FOR_COUT_ITR != END_FOR_COUT_ITR ) ? OS : OS << " "; } } OS

// 入出力用
template <class Traits> inline basic_istream<char,Traits>& VariadicCin( basic_istream<char,Traits>& is ) { return is; }
template <class Traits , typename Arg , typename... ARGS> inline basic_istream<char,Traits>& VariadicCin( basic_istream<char,Traits>& is , Arg& arg , ARGS&... args ) { return VariadicCin( is >> arg , args... ); }
template <class Traits> inline basic_istream<char,Traits>& VariadicGetline( basic_istream<char,Traits>& is , const char& separator ) { return is; }
template <class Traits , typename Arg , typename... ARGS> inline basic_istream<char,Traits>& VariadicGetline( basic_istream<char,Traits>& is , const char& separator , Arg& arg , ARGS&... args ) { return VariadicGetline( getline( is , arg , separator ) , separator , args... ); }
template <class Traits , typename Arg> inline basic_ostream<char,Traits>& VariadicCout( basic_ostream<char,Traits>& os , const Arg& arg ) { return os << arg; }
template <class Traits , typename Arg1 , typename Arg2 , typename... ARGS> inline basic_ostream<char,Traits>& VariadicCout( basic_ostream<char,Traits>& os , const Arg1& arg1 , const Arg2& arg2 , const ARGS&... args ) { return VariadicCout( os << arg1 << " " , arg2 , args... ); }

// 二分探索テンプレート
// EXPRESSIONがANSWERの広義単調関数の時、EXPRESSION >= TARGETの整数解を格納。
#define BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , DESIRED_INEQUALITY , TARGET , INEQUALITY_FOR_CHECK , UPDATE_U , UPDATE_L , UPDATE_ANSWER ) \
  static_assert( ! is_same<TYPE_OF( TARGET ),uint>::value && ! is_same<TYPE_OF( TARGET ),ull>::value ); \
  ll ANSWER = MINIMUM;							\
  ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM;				\
  ll VARIABLE_FOR_BINARY_SEARCH_U = MAXIMUM;				\
  ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
  ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH;				\
  while( VARIABLE_FOR_BINARY_SEARCH_L < VARIABLE_FOR_BINARY_SEARCH_U ){ \
    VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( EXPRESSION ) - ( TARGET ); \
    CERR( "二分探索中：" , VARIABLE_FOR_BINARY_SEARCH_L , "<=" , ANSWER , "<=" , VARIABLE_FOR_BINARY_SEARCH_U , ":" , EXPRESSION , "-" , TARGET , "=" , VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ); \
    if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH INEQUALITY_FOR_CHECK 0 ){ \
      VARIABLE_FOR_BINARY_SEARCH_U = UPDATE_U;				\
    } else {								\
      VARIABLE_FOR_BINARY_SEARCH_L = UPDATE_L;				\
    }									\
    ANSWER = UPDATE_ANSWER;						\
  }									\
  if( VARIABLE_FOR_BINARY_SEARCH_L > VARIABLE_FOR_BINARY_SEARCH_U ){	\
    CERR( "二分探索失敗：" , VARIABLE_FOR_BINARY_SEARCH_L , ">" , VARIABLE_FOR_BINARY_SEARCH_U ); \
    ANSWER = MAXIMUM + 1;						\
  } else {								\
    CERR( "二分探索終了：" , VARIABLE_FOR_BINARY_SEARCH_L , "<=" , ANSWER , "<=" , VARIABLE_FOR_BINARY_SEARCH_U , ":" , EXPRESSION , ( EXPRESSION > TARGET ? ">" : EXPRESSION < TARGET ? "<" : "=" ) , TARGET ); \
    if( EXPRESSION DESIRED_INEQUALITY TARGET ){				\
      CERR( "二分探索成功：" , #ANSWER , "=" , ANSWER );			\
    } else {								\
      CERR( "二分探索失敗：" , EXPRESSION , "<>"[EXPRESSION > TARGET],  TARGET ); \
      ANSWER = MAXIMUM + 1;						\
    }									\
  }									\

// 単調増加の時にEXPRESSION >= TARGETの最小解を格納。
#define BS1( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET )		\
  BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , >= , TARGET , >= , ANSWER , ANSWER + 1 , ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2 ) \

// 単調増加の時にEXPRESSION <= TARGETの最大解を格納。
#define BS2( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET )		\
  BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , <= , TARGET , > , ANSWER - 1 , ANSWER , ( VARIABLE_FOR_BINARY_SEARCH_L + 1 + VARIABLE_FOR_BINARY_SEARCH_U ) / 2 ) \

// 単調減少の時にEXPRESSION >= TARGETの最大解を格納。
#define BS3( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET )		\
  BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , >= , TARGET , < , ANSWER - 1 , ANSWER , ( VARIABLE_FOR_BINARY_SEARCH_L + 1 + VARIABLE_FOR_BINARY_SEARCH_U ) / 2 ) \

// 単調減少の時にEXPRESSION <= TARGETの最小解を格納。
#define BS4( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET )		\
  BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , <= , TARGET , <= , ANSWER , ANSWER + 1 , ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2 ) \

// グリッド問題用
int H , W , H_minus , W_minus , HW;
vector<vector<bool> > non_wall;
inline T2<int> EnumHW( const int& v ) { return { v / W , v % W }; }
inline int EnumHW_inv( const int& h , const int& w ) { return h * W + w; }

// グラフ用関数
template <typename PATH> list<PATH> E( const int& i );
template <typename PATH> vector<list<PATH> > e;

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

// Resetはm_foundとm_prevを初期化
// Shiftはm_foundとm_prevを非初期化
// Breadth/DepthFirstConnectedComponentSearchは無向グラフの連結成分を色分け＆数え上げ

// Next()の反復でm_initから到達可能な頂点を全探索。
// 計算量O((m_initの連結成分)+(m_initの連結成分におけるEのサイズの合計))
#define DECLARATION_OF_FIRST_SEARCH( BREADTH )				\
  template <int V_max>							\
  class BREADTH ## FirstSearch_Body					\
  {									\
									\
  protected:								\
    int m_V;								\
    int m_init;								\
    list<int> m_next;							\
    bool m_found[V_max];						\
    int m_prev[V_max];							\
									\
  public:								\
    inline BREADTH ## FirstSearch_Body( const int& V );			\
    inline BREADTH ## FirstSearch_Body( const int& V , const int& init ); \
									\
    inline void Reset( const int& init );				\
    inline void Shift( const int& init );				\
									\
    inline const int& size() const;					\
    inline const int& init() const;					\
    inline bool& found( const int& i );					\
    inline const int& prev( const int& i ) const;			\
									\
    int Next();								\
									\
  private:								\
    virtual list<int> e( const int& t ) = 0;				\
									\
  };									\
									\
  template <int V_max,list<int> E(const int&)>				\
  class BREADTH ## FirstSearch :					\
    public BREADTH ## FirstSearch_Body<V_max>				\
  {									\
									\
  public:								\
    template<typename... Args> inline BREADTH ## FirstSearch( const Args&... args ); \
									\
  private:								\
    inline list<int> e( const int& t );					\
									\
  };									\
									\
  template <int V_max,list<int> E(const int&)> void BREADTH ## FirstConnectedComponentSearch( const int& V , int ( &cc_numx )[V_max] , int& count ); \

#define DEFINITION_OF_FIRST_SEARCH( BREADTH , PUSH )			\
  template <int V_max> inline BREADTH ## FirstSearch_Body<V_max>::BREADTH ## FirstSearch_Body( const int& V ) : m_V( V ) , m_init() , m_next() , m_found() , m_prev() { assert( m_V <= V_max ); for( int i = 0 ; i < m_V ; i++ ){ m_prev[i] = -1; } } \
  template <int V_max> inline BREADTH ## FirstSearch_Body<V_max>::BREADTH ## FirstSearch_Body( const int& V , const int& init ) : BREADTH ## FirstSearch_Body( V ) { m_init = init; m_next.push_back( m_init ); m_found[m_init] = true; } \
  template <int V_max,list<int> E(const int&)> template <typename... Args> inline BREADTH ## FirstSearch<V_max,E>::BREADTH ## FirstSearch( const Args&... args ) : BREADTH ## FirstSearch_Body<V_max>( args... ) {} \
									\
  template <int V_max> inline void BREADTH ## FirstSearch_Body<V_max>::Reset( const int& init ) { m_init = init; assert( m_init < m_V ); m_next.clear(); m_next.push_back( m_init ); for( int i = 0 ; i < m_V ; i++ ){ m_found[i] = i == m_init; m_prev[i] = -1; } } \
  template <int V_max> inline void BREADTH ## FirstSearch_Body<V_max>::Shift( const int& init ) { m_init = init; assert( m_init < m_V ); m_next.clear(); if( ! m_found[m_init] ){ m_next.push_back( m_init ); m_found[m_init] = true; } } \
									\
  template <int V_max> inline const int& BREADTH ## FirstSearch_Body<V_max>::size() const { return m_V; } \
  template <int V_max> inline const int& BREADTH ## FirstSearch_Body<V_max>::init() const { return m_init; } \
  template <int V_max> inline bool& BREADTH ## FirstSearch_Body<V_max>::found( const int& i ) { assert( i < m_V ); return m_found[i]; } \
  template <int V_max> inline const int& BREADTH ## FirstSearch_Body<V_max>::prev( const int& i ) const { assert( i < m_V ); return m_prev[i]; } \
									\
  template <int V_max>							\
  int BREADTH ## FirstSearch_Body<V_max>::Next()			\
  {									\
									\
    if( m_next.empty() ){						\
									\
      return -1;							\
									\
    }									\
									\
    const int i_curr = m_next.front();					\
    m_next.pop_front();							\
    list<int> edge = e( i_curr );					\
									\
    while( ! edge.empty() ){						\
									\
      const int& i = edge.front();					\
      bool& found_i = m_found[i];					\
									\
      if( ! found_i ){							\
									\
	m_next.PUSH( i );						\
	m_prev[i] = i_curr;						\
	found_i = true;							\
									\
      }									\
									\
      edge.pop_front();							\
									\
    }									\
									\
    return i_curr;							\
									\
  }									\
									\
  template <int V_max,list<int> E(const int&)> inline list<int> BREADTH ## FirstSearch<V_max,E>::e( const int& t ) { return E( t ); } \
									\
  template <int V_max,list<int> E(const int&)> void BREADTH ## FirstConnectedComponentSearch( const int& V , int ( &cc_num )[V_max] , int& count ) \
  {									\
									\
    BREADTH ## FirstSearch<V_max,E> bfs{ V };				\
    count = 0;								\
									\
    for( int i = 0 ; i < V ; i++ ){					\
									\
      cc_num[i] = -1;							\
									\
    }									\
									\
    for( int i = 0 ; i < V ; i++ ){					\
									\
      if( cc_num[i] == -1 ){						\
									\
	bfs.Shift( i );							\
	int j = bfs.Next();						\
									\
	while( j != -1 ? cc_num[j] == -1 : false ){			\
									\
	  cc_num[j] = count;						\
	  j = bfs.Next();						\
									\
	}								\
									\
	count++;							\
									\
      }									\
									\
    }									\
									\
    return;								\
									\
  }									\

DECLARATION_OF_FIRST_SEARCH( Breadth );
DEFINITION_OF_FIRST_SEARCH( Breadth , push_back );

vector<vector<vector<int> > > f{};
template <typename PATH> list<PATH> E( const int& i )
{
  list<PATH> answer{};
  // list<PATH> answer = e<PATH>[i];
  // VVV 入力によらない処理は以下に挿入する。
  auto [x,c] = EnumHW( i );
  auto& e_x = e<int>[x];
  FOR_ITR( e_x ){
    int y = min( x , *itr );
    int z = max( x , *itr );
    if( f[z][y].empty() ? false : f[z][y][c] >= 0 ){
      answer.push_back( EnumHW_inv( *itr , f[z][y][c] ) );
    }
  }
  // AAA 入力によらない処理は以上に挿入する。
  return answer;
}

inline void Solve()
{
  CEXPR( int , bound_N , 10 ); // 0が1個
  CIN_ASSERT( N , 2 , bound_N );
  CIN_ASSERT( M , 1 , N * ( N - 1 ) / 2 );
  DEXPR( int , bound_C , 100000 , 10 ); // 0が5個
  CIN_ASSERT( C , 1 , bound_C );
  H = N;
  W = C + 1;
  H_minus = H - 1;
  HW = H * W;
  e<int>.resize( N );
  f.resize( N );
  FOR( j , 0 , N ){
    f[j].resize( j );
  }
  FOR( m , 0 , M ){
    CIN_ASSERT( i , 1 , N );
    CIN_ASSERT( j , i + 1 , N );
    CIN_ASSERT( r , 1 , C );
    CIN_ASSERT( w , 1 , C );
    --i;
    --j;
    e<int>[i].push_back( j );
    e<int>[j].push_back( i );
    f[j][i].resize( W );
    FOREQ( c , 0 , C ){
      f[j][i][c] = max( -1 , c - c / r - w );
    }
  }
  BreadthFirstSearch<bound_N * ( bound_C + 1 ),E<int>> bfs{ HW };
  FOREQ( c , 1 , C ){
    bfs.Shift( EnumHW_inv( 0 , c ) );
    while( bfs.Next() != -1 ){}
    if( !bfs.found( EnumHW_inv( H_minus , 0 ) ) ){
      COUT( -1 );
    } else {
      BS3( answer , 0 , C , ( bfs.found( EnumHW_inv( H_minus , answer ) ) ? 1 : 0 ) , 1 );
      COUT( answer );
    }
  }
}

REPEAT_MAIN(1);
0