#922130 (C++17) No.2531 Coloring Vertices on Namori

提出ソース

結果

問題	No.2531 Coloring Vertices on Namori
ユーザー	👑 p-adic
提出日時	2023-10-24 09:17:29
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	393 ms / 2,000 ms
コード長	15,720 bytes
コンパイル時間	3,918 ms
コンパイル使用メモリ	232,448 KB
実行使用メモリ	56,592 KB
最終ジャッジ日時	2023-10-24 09:17:44
合計ジャッジ時間	14,413 ms
ジャッジサーバーID （参考情報）	judge13 / judge14

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	3 ms 4,680 KB
testcase_01	AC	3 ms 4,680 KB
testcase_02	AC	3 ms 4,680 KB
testcase_03	AC	2 ms 4,680 KB
testcase_04	AC	3 ms 4,680 KB
testcase_05	AC	129 ms 50,256 KB
testcase_06	AC	2 ms 4,680 KB
testcase_07	AC	131 ms 50,256 KB
testcase_08	AC	309 ms 50,256 KB
testcase_09	AC	345 ms 50,256 KB
testcase_10	AC	317 ms 50,256 KB
testcase_11	AC	237 ms 56,592 KB
testcase_12	AC	233 ms 56,592 KB
testcase_13	AC	240 ms 56,592 KB
testcase_14	AC	295 ms 50,256 KB
testcase_15	AC	299 ms 50,256 KB
testcase_16	AC	300 ms 50,256 KB
testcase_17	AC	2 ms 4,680 KB
testcase_18	AC	3 ms 4,680 KB
testcase_19	AC	3 ms 4,680 KB
testcase_20	AC	393 ms 50,288 KB
testcase_21	AC	349 ms 50,256 KB
testcase_22	AC	354 ms 50,520 KB
testcase_23	AC	381 ms 50,256 KB
testcase_24	AC	355 ms 50,256 KB
testcase_25	AC	358 ms 50,256 KB
testcase_26	AC	355 ms 50,256 KB
testcase_27	AC	363 ms 50,256 KB
testcase_28	AC	358 ms 50,256 KB
testcase_29	AC	357 ms 50,256 KB
testcase_30	AC	388 ms 50,256 KB
testcase_31	AC	357 ms 50,256 KB
testcase_32	AC	357 ms 50,256 KB
testcase_33	AC	383 ms 50,256 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 uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using lld = __float128;
template <typename INT> using T2 = pair<INT,INT>;
template <typename INT> using T3 = tuple<INT,INT,INT>;
template <typename INT> using T4 = tuple<INT,INT,INT,INT>;
#define SET_TESTCASE_NUM SET_ASSERT( test_case_num , 1 , bound_test_case_num );
// #define #define SET_TESTCASE_NUM GETLINE_COUNT( test_case_num_str , 1 , " " ); STOI( test_case_num_str , test_case_num_prep , bound_test_case_num ); test_case_num = test_case_num_prep
#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_TESTCASE_NUM; } REPEAT( test_case_num ){ if constexpr( bound_test_case_num > 1 ){ CERR( "testcase " , VARIABLE_FOR_REPEAT_test_case_num , ":" ); } Solve(); CERR( "" ); } CHECK_REDUNDANT_INPUT; }
#define START_WATCH chrono::system_clock::time_point watch = chrono::system_clock::now()
#define CURRENT_TIME static_cast<double>( chrono::duration_cast<chrono::microseconds>( chrono::system_clock::now() - watch ).count() / 1000.0 )
#define CHECK_WATCH( TL_MS ) ( CURRENT_TIME < TL_MS - 100.0 )
#define TYPE_OF( VAR ) decay_t<decltype( VAR )>
#define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE
#define CIN( LL , ... ) LL __VA_ARGS__; VariadicCin( cin , __VA_ARGS__ )
#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 SET_A( A , N ) SOLVE_ONLY; FOR( VARIABLE_FOR_CIN_A , 0 , N ){ cin >> A[VARIABLE_FOR_CIN_A]; }
#define CIN_A( LL , A , N ) vector<LL> A( N ); SET_A( A , N );
#define GETLINE_SEPARATE( SEPARATOR , ... ) string __VA_ARGS__; VariadicGetline( cin , SEPARATOR , __VA_ARGS__ )
#define GETLINE( ... ) GETLINE_SEPARATE( '\n' , __VA_ARGS__ )
#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 SET_PRECISION( DECIMAL_DIGITS ) cout << fixed << setprecision( DECIMAL_DIGITS )
#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
#define RETURN( ... ) COUT( __VA_ARGS__ ); return

// 入出力用
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... ); }

#define POWER_MOD( ANSWER , ARGUMENT , EXPONENT , MODULO )		\
  ll ANSWER{ 1 };							\
  {									\
    ll ARGUMENT_FOR_SQUARE_FOR_POWER = ( ( ARGUMENT ) % ( MODULO ) ) % ( MODULO ); \
    ARGUMENT_FOR_SQUARE_FOR_POWER < 0 ? ARGUMENT_FOR_SQUARE_FOR_POWER += ( MODULO ) : ARGUMENT_FOR_SQUARE_FOR_POWER; \
    TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT );	\
    while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){			\
      if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){			\
	ANSWER = ( ANSWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % ( MODULO ); \
      }									\
      ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT_FOR_SQUARE_FOR_POWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % ( MODULO ); \
      EXPONENT_FOR_SQUARE_FOR_POWER /= 2;				\
    }									\
  }									\

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

// 入力フォーマットチェック用
// 1行中の変数の個数をSEPARATOR区切りで確認
#define GETLINE_COUNT( S , VARIABLE_NUMBER , SEPARATOR ) GETLINE( S ); int VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S = 0; int VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S  = S.size(); { int size = S.size(); int count = 0; for( int i = 0 ; i < size ; i++ ){ if( S.substr( i , 1 ) == SEPARATOR ){ count++; } } assert( count + 1 == VARIABLE_NUMBER ); }
// 余計な入力の有無を確認
#ifdef DEBUG
  #define CHECK_REDUNDANT_INPUT 
#else
  #define CHECK_REDUNDANT_INPUT string VARIABLE_FOR_CHECK_REDUNDANT_INPUT = ""; cin >> VARIABLE_FOR_CHECK_REDUNDANT_INPUT; assert( VARIABLE_FOR_CHECK_REDUNDANT_INPUT == "" ); assert( ! cin )
  // #define CHECK_REDUNDANT_INPUT string VARIABLE_FOR_CHECK_REDUNDANT_INPUT = ""; getline( cin , VARIABLE_FOR_CHECK_REDUNDANT_INPUT ); assert( VARIABLE_FOR_CHECK_REDUNDANT_INPUT == "" ); assert( ! cin )
#endif
// |N| <= BOUNDを満たすNをSから構築
#define STOI( S , N , BOUND ) TYPE_OF( BOUND ) N = 0; { bool VARIABLE_FOR_POSITIVITY_FOR_GETLINE = true; assert( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ); if( S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) == "-" ){ VARIABLE_FOR_POSITIVITY_FOR_GETLINE = false; VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; assert( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ); } assert( S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) != " " ); string VARIABLE_FOR_LETTER_FOR_GETLINE{}; int VARIABLE_FOR_DIGIT_FOR_GETLINE{}; while( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ? ( VARIABLE_FOR_LETTER_FOR_GETLINE = S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) ) != " " : false ){ VARIABLE_FOR_DIGIT_FOR_GETLINE = stoi( VARIABLE_FOR_LETTER_FOR_GETLINE ); assert( N < BOUND / 10 ? true : N == BOUND / 10 && VARIABLE_FOR_DIGIT_FOR_GETLINE <= BOUND % 10 ); N = N * 10 + VARIABLE_FOR_DIGIT_FOR_GETLINE; VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; } if( ! VARIABLE_FOR_POSITIVITY_FOR_GETLINE ){ N *= -1; } if( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ){ VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; } }
// SをSEPARATORで区切りTを構築
#define SEPARATE( S , T , SEPARATOR ) string T{}; { assert( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ); int VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S_prev = VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S; assert( S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) != SEPARATOR ); string VARIABLE_FOR_LETTER_FOR_GETLINE{}; while( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ? ( VARIABLE_FOR_LETTER_FOR_GETLINE = S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) ) != SEPARATOR : false ){ VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; } T = S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S_prev , VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S - VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S_prev ); if( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ){ VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; } }

// 圧縮用
#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&

// 連結性の制約確認用のBFSライブラリ
#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;}

// グラフ用関数
template <typename PATH> vector<list<PATH> > e;
template <typename PATH> list<PATH> E( const int& i )
{
  // list<PATH> answer{};
  list<PATH> answer = e<PATH>[i];
  // VVV 入力によらない処理は以下に挿入する。

  // AAA 入力によらない処理は以上に挿入する。
  return answer;
}

inline void Solve()
{
  DEXPR( int , bound_N , 200000 , 100 ); // 0が5個
  CIN_ASSERT( N , 3 , bound_N );
  CEXPR( int , bound_K , 200000 ); // 0が5個
  CIN_ASSERT( K , 2 , bound_K );
  CEXPR( ll , P , 998244353 );

  // グラフ
  e<int>.resize( N );
  set<int> edge[N]{};
  FOR( j , 0 , N ){
    CIN_ASSERT( uj , 1 , N );
    CIN_ASSERT( vj , uj + 1 , N );
    uj--;
    vj--;
    assert( edge[uj].count( vj ) == 0 );
    edge[uj].insert( vj );
    edge[vj].insert( uj );
    e<int>[uj].push_back( vj );
    e<int>[vj].push_back( uj );
  }
  CHECK_REDUNDANT_INPUT;
  
  // 連結性の制約確認
  int cc_num[bound_N];
  int count = 0;
  BreadthFirstConnectedComponentSearch<bound_N,E>( N , cc_num , count );
  assert( count == 1 );
  
  int length = N;
  FOR( i , 0 , N ){
    if( edge[i].size() == 1 ){
      int r = i;
      while( edge[r].size() == 1 ){
	length--;
	int j = *( edge[r].begin() );
	edge[j].erase( r );
	edge[r].erase( j );
	r = j;
      }
    }
  }
  POWER_MOD( temp , K - 1 , N - length + 1 , P );
  ( temp *= K ) %= P;
  ll answer = temp;
  FOREQ( i , 3 , length ){
    ( temp *= K - 1 ) %= P;
    ( answer = temp - answer ) < 0 ? answer += P : answer;
  }
  RETURN( answer );
}

REPEAT_MAIN(1);

yukicoder

結果

テストケース

ソースコード