#920689 (C++17) No.2916 累進コスト最小化

提出ソース

結果

問題	No.2916 累進コスト最小化
ユーザー	👑 p-adic
提出日時	2023-10-20 00:28:19
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	454 ms / 3,500 ms
コード長	8,106 bytes
コンパイル時間	3,051 ms
コンパイル使用メモリ	227,368 KB
実行使用メモリ	74,624 KB
最終ジャッジ日時	2024-10-05 01:05:36
合計ジャッジ時間	7,842 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	454 ms 74,496 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	1 ms 6,820 KB
testcase_03	AC	2 ms 6,820 KB
testcase_04	AC	1 ms 6,816 KB
testcase_05	AC	2 ms 6,820 KB
testcase_06	AC	2 ms 6,816 KB
testcase_07	AC	2 ms 6,820 KB
testcase_08	AC	2 ms 6,816 KB
testcase_09	AC	1 ms 6,816 KB
testcase_10	AC	1 ms 6,816 KB
testcase_11	AC	1 ms 6,816 KB
testcase_12	AC	1 ms 6,816 KB
testcase_13	AC	2 ms 6,820 KB
testcase_14	AC	1 ms 6,816 KB
testcase_15	AC	2 ms 6,816 KB
testcase_16	AC	2 ms 6,816 KB
testcase_17	AC	1 ms 6,816 KB
testcase_18	AC	2 ms 6,820 KB
testcase_19	AC	1 ms 6,816 KB
testcase_20	AC	2 ms 6,820 KB
testcase_21	AC	1 ms 6,816 KB
testcase_22	AC	2 ms 6,820 KB
testcase_23	AC	1 ms 6,816 KB
testcase_24	AC	168 ms 62,760 KB
testcase_25	AC	166 ms 62,752 KB
testcase_26	AC	217 ms 69,828 KB
testcase_27	AC	216 ms 70,624 KB
testcase_28	AC	210 ms 66,628 KB
testcase_29	AC	220 ms 70,628 KB
testcase_30	AC	153 ms 57,288 KB
testcase_31	AC	210 ms 64,356 KB
testcase_32	AC	448 ms 74,500 KB
testcase_33	AC	446 ms 74,624 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
#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 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... ); }

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

// 入力の範囲内で要件
// (1) (T,A_T:T^2->T)がmeet半束（可換羃等半群）である。
//     （以下A_Tの定める等号つき半順序を<=と置く）
// (2) (T,m_T:T^2->T)が半群である。
// (3) m_TがA_T上分配的、つまり
//     - Tの任意の要素s,t,uに対し
//       - m_T(u,A_T(s,t)) = A_T(m_T(u,s),m_T(u,t)) 
//       - m_T(A_T(s,t),u) = A_T(m_T(s,u),m_T(t,u))
//     である。
// (4) inftyでないdの値はnon-negative、つまり
//     - Tの任意の要素sとinftyでないdの任意の値tに対し
//       - s<=m_T(s,t) 
//       - s<=m_T(t,s)
//     である。
// (5) inftyでないdの値size_max個以下のm_Tに関する積でinftyが表せない。
// が成り立つ場合にのみサポート。

// ただし<=が等号つき全順序である場合、(3)は
// (3)' m_Tが<=に関する半順序半群演算、つまり
//     - Tの任意の要素s,t,uに対しs<=tならば
//       - m_T(u,s) <= m_T(u,t) 
//       - m_T(s,u) <= m_T(t,u)
//     である。
// と同値であることに注意。

// O(size_max^3)で全経路の重み（edgeごとの重みのm_Tに関する積）の
// A_Tに関する下限（多変数化したA_Tへの適用値）を計算。
template <typename T , T m_T(const T&,const T&) , T A_T(const T&,const T&) , int size_max>
void FloydWarshall( const T ( &d )[size_max][size_max] , T ( &weight )[size_max][size_max] , const int& size , const T& infty )
{

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

    T ( &weight_i )[size_max] = weight[i];
    const T ( &d_i )[size_max] = d[i];
    
    for( int j = 0 ; j < size ; j++ ){

      weight_i[j] = d_i[j];

    }

  }

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

    T ( &weight_k )[size_max] = weight[k];

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

      T ( &weight_i )[size_max] = weight[i];
      const T& weight_ik = weight_i[k];
    
      if( i != k && weight_ik != infty ){
	
	for( int j = 0 ; j < size ; j++ ){

	  const T& weight_kj = weight_k[j];

	  if( i != j && k != j && weight_kj != infty ){

	    T& weight_ij = weight_i[j];
	    const T weight_curr = m_T( weight_ik , weight_kj );
	    weight_ij = weight_ij == infty ? weight_curr : A_T( weight_ij , weight_curr );

	  }

	}

      }

    }

  }

  return;

}

int C_plus;
vector<int> infty{};
inline vector<int> m( const vector<int>& f0 , const vector<int>& f1 ) { vector<int> answer( C_plus ); FOR( c , 0 , C_plus ){ answer[c] = f0[c] >= 0 ? f1[f0[c]] : -1; } return answer; }
inline vector<int> A( const vector<int>& f0 , const vector<int>& f1 ) { vector<int> answer( C_plus ); FOR( c , 0 , C_plus ){ answer[c] = max( f0[c] , f1[c] ); } 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 );
  CEXPR( int , bound_C , 100000 ); // 0が5個
  CIN_ASSERT( C , 1 , bound_C );
  C_plus = C + 1;
  vector<int> d[bound_N][bound_N] = {};
  bool found[bound_N][bound_N] = {};
  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 );
    assert( !found[--i][--j] );
    found[i][j] = true;
    d[i][j].resize( C_plus );
    d[j][i].resize( C_plus );
    FOREQ( c , 0 , C ){
      d[i][j][c] = d[j][i][c] = max( -1 , c - c / r - w );
    }
  }
  vector<int> weight[bound_N][bound_N];
  FloydWarshall<vector<int>,m,A,bound_N>( d , weight , N , infty );
  if( weight[0][N-1] == infty ){
    FOREQ( c , 1 , C ){
      COUT( -1 );
    }
  } else {
    FOREQ( c , 1 , C ){
      COUT( weight[0][N-1][c] );
    }
  }
}

REPEAT_MAIN(1);

yukicoder

結果

テストケース

ソースコード