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

提出ソース

結果

問題	No.2916 累進コスト最小化
ユーザー	👑 p-adic
提出日時	2023-10-20 21:14:17
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	10,797 bytes
コンパイル時間	3,608 ms
コンパイル使用メモリ	237,384 KB
実行使用メモリ	15,480 KB
最終ジャッジ日時	2024-09-21 13:41:50
合計ジャッジ時間	8,894 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	3 ms 15,480 KB
testcase_01	AC	3 ms 8,260 KB
testcase_02	AC	3 ms 8,236 KB
testcase_03	AC	3 ms 8,372 KB
testcase_04	AC	3 ms 8,260 KB
testcase_05	AC	3 ms 8,516 KB
testcase_06	AC	4 ms 8,392 KB
testcase_07	AC	4 ms 8,260 KB
testcase_08	AC	3 ms 8,348 KB
testcase_09	AC	4 ms 8,244 KB
testcase_10	AC	4 ms 8,328 KB
testcase_11	AC	4 ms 8,312 KB
testcase_12	AC	3 ms 8,180 KB
testcase_13	AC	4 ms 8,324 KB
testcase_14	AC	3 ms 8,260 KB
testcase_15	AC	3 ms 8,348 KB
testcase_16	AC	4 ms 8,284 KB
testcase_17	AC	4 ms 8,392 KB
testcase_18	AC	3 ms 8,196 KB
testcase_19	AC	3 ms 8,300 KB
testcase_20	AC	3 ms 8,216 KB
testcase_21	AC	4 ms 8,232 KB
testcase_22	AC	4 ms 8,212 KB
testcase_23	TLE	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-

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

ソースコード

raw source code

// 誤解法（O(N^2 C + C^2)BFS）チェック
#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;
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... ); }

// グリッド問題用
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


// 圧縮用
#define TE template
#define TY typename
#define US using
#define ST static
#define IN inline
#define CL class
#define PU public
#define OP operator
#define CE constexpr
#define CO const
#define NE noexcept
#define RE return 
#define WH while
#define VO void
#define VE vector
#define LI list
#define BE begin
#define EN end
#define SZ size
#define MO move
#define TH this
#define CRI CO int&
#define CRUI CO uint&
#define CRL CO ll&

#define DC_OF_FIRST_SEARCH(BREADTH)TE <int V_max> CL BREADTH ## FirstSearch_Body{PU:int m_V;int m_init;LI<int> m_next;bool m_found[V_max];int m_prev[V_max];IN BREADTH ## FirstSearch_Body(CRI V);IN BREADTH ## FirstSearch_Body(CRI V,CRI init);IN VO Reset(CRI init);IN VO Shift(CRI init);IN CRI SZ()CO;IN CRI init()CO;IN bool& found(CRI i);IN CRI prev(CRI i)CO;int Next();virtual LI<int> e(CRI t)= 0;};TE <int V_max,LI<int> E(CRI)> CL BREADTH ## FirstSearch:PU BREADTH ## FirstSearch_Body<V_max>{PU:TE<TY... Args> IN BREADTH ## FirstSearch(CO Args&... args);IN LI<int> e(CRI t);};TE <int V_max,LI<int> E(CRI)> VO BREADTH ## FirstConnectedComponent(CRI V,int(&cc_num)[V_max],int& count);
#define DF_OF_FIRST_SEARCH(BREADTH,PUSH)TE <int V_max> IN BREADTH ## FirstSearch_Body<V_max>::BREADTH ## FirstSearch_Body(CRI 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;}}TE <int V_max> IN BREADTH ## FirstSearch_Body<V_max>::BREADTH ## FirstSearch_Body(CRI V,CRI init):BREADTH ## FirstSearch_Body(V){m_init = init;m_next.push_back(m_init);m_found[m_init] = true;}TE <int V_max,LI<int> E(CRI)> TE <TY... Args> IN BREADTH ## FirstSearch<V_max,E>::BREADTH ## FirstSearch(CO Args&... args):BREADTH ## FirstSearch_Body<V_max>(args...){}TE <int V_max> IN VO BREADTH ## FirstSearch_Body<V_max>::Reset(CRI 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;}}TE <int V_max> IN VO BREADTH ## FirstSearch_Body<V_max>::Shift(CRI 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;}}TE <int V_max> IN CRI BREADTH ## FirstSearch_Body<V_max>::SZ()CO{RE m_V;}TE <int V_max> IN CRI BREADTH ## FirstSearch_Body<V_max>::init()CO{RE m_init;}TE <int V_max> IN bool& BREADTH ## FirstSearch_Body<V_max>::found(CRI i){assert(i < m_V);RE m_found[i];}TE <int V_max> IN CRI BREADTH ## FirstSearch_Body<V_max>::prev(CRI i)CO{assert(i < m_V);RE m_prev[i];}TE <int V_max> int BREADTH ## FirstSearch_Body<V_max>::Next(){if(m_next.empty()){RE -1;}CO int i_curr = m_next.front();m_next.pop_front();LI<int> edge = e(i_curr);WH(! edge.empty()){CRI 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();}RE i_curr;}TE <int V_max,LI<int> E(CRI)> IN LI <int> BREADTH ## FirstSearch<V_max,E>::e(CRI t){RE E(t);}TE <int V_max,LI<int> E(CRI)> VO BREADTH ## FirstConnectedComponentSearch(CRI 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();WH(j != -1?cc_num[j] == -1:false){cc_num[j] = count;j = bfs.Next();}count++;}}RE;}
DC_OF_FIRST_SEARCH(Breadth);DF_OF_FIRST_SEARCH(Breadth,push_back);
TE <int V_max,LI<int> E(CRI)>VO SetDepth_Body(BreadthFirstSearch<V_max,E>& bfs,CRI V,int ( &depth )[V_max]){for(int i = 0;i < V;i++){depth[i] = -1;}int i = bfs.Next();depth[i] = 0;WH((i = bfs.Next())!= -1){depth[i] = depth[bfs.prev( i )] + 1;}RE;}TE <int V_max,LI<int> E(CRI)>VO SetDepth(CRI V,CRI init,int ( &depth )[V_max]){BreadthFirstSearch<V_max,E> bfs{V,init};SetDepth_Body(bfs,V,depth);RE;}TE <int V_max,LI<int> E(CRI)>VO SetDepth(BreadthFirstSearch<V_max,E>& bfs,CRI V,CRI init,int ( &depth )[V_max]){bfs.Reset(init);SetDepth_Body(bfs,V,depth);RE;}

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 );
  CEXPR( int , bound_C , 100000 ); // 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 ){}
    bool found = false;
    FOREQINV( d , C , 0 ){
      if( bfs.found( EnumHW_inv( H_minus , d ) ) ){
	found = true;
	COUT( d );
	break;
      }
    }
    if( ! found ){
      COUT( -1 );
    }
  }
}

REPEAT_MAIN(1);

yukicoder

結果

テストケース

ソースコード