結果
問題 | No.2563 色ごとのグループ |
ユーザー | 👑 p-adic |
提出日時 | 2024-01-02 01:45:17 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 75 ms / 2,000 ms |
コード長 | 17,864 bytes |
コンパイル時間 | 3,704 ms |
コンパイル使用メモリ | 235,328 KB |
実行使用メモリ | 14,624 KB |
最終ジャッジ日時 | 2024-09-27 17:38:15 |
合計ジャッジ時間 | 5,424 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 1 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 1 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,944 KB |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | AC | 1 ms
6,940 KB |
testcase_11 | AC | 1 ms
6,944 KB |
testcase_12 | AC | 2 ms
6,940 KB |
testcase_13 | AC | 2 ms
6,944 KB |
testcase_14 | AC | 2 ms
6,940 KB |
testcase_15 | AC | 2 ms
6,940 KB |
testcase_16 | AC | 2 ms
6,940 KB |
testcase_17 | AC | 2 ms
6,940 KB |
testcase_18 | AC | 2 ms
6,940 KB |
testcase_19 | AC | 3 ms
6,940 KB |
testcase_20 | AC | 5 ms
6,940 KB |
testcase_21 | AC | 4 ms
6,944 KB |
testcase_22 | AC | 4 ms
6,940 KB |
testcase_23 | AC | 6 ms
6,944 KB |
testcase_24 | AC | 35 ms
7,808 KB |
testcase_25 | AC | 29 ms
8,320 KB |
testcase_26 | AC | 38 ms
11,168 KB |
testcase_27 | AC | 35 ms
13,980 KB |
testcase_28 | AC | 45 ms
12,076 KB |
testcase_29 | AC | 64 ms
14,624 KB |
testcase_30 | AC | 62 ms
14,624 KB |
testcase_31 | AC | 63 ms
14,624 KB |
testcase_32 | AC | 63 ms
14,492 KB |
testcase_33 | AC | 72 ms
13,564 KB |
testcase_34 | AC | 74 ms
13,604 KB |
testcase_35 | AC | 72 ms
13,684 KB |
testcase_36 | AC | 75 ms
13,600 KB |
testcase_37 | AC | 75 ms
13,616 KB |
ソースコード
#ifdef INCLUDE_MAINinline void Solve(){CIN( ll , N , M );CIN_A( int , C , N );UnionFindForest<int> uff( N );e<int>.resize( N );FOR( j , 0 , M ){CIN( int , uj , vj );uj--;vj--;if( C[uj] == C[vj] ){uff.Graft( uj , vj );}}uint answer = 0;uint count[N+1]{};vector<uint> root{};uff.SetRoot( root );const uint& size = uff.SizeOfRoot();FOR( i , 0 , size ){count[C[root[i]]]++;}FOREQ( i , 1 , N ){count[i] > 0 ? answer += count[i] - 1 : answer;}RETURN( answer );}REPEAT_MAIN(1);#else // INCLUDE_MAIN#ifdef INCLUDE_SUBtemplate <typename PATH> list<PATH> E( const int& i ){// list<PATH> answer{};list<PATH> answer = e<PATH>[i];// VVV 入力によらない処理は以下に挿入する。// AAA 入力によらない処理は以上に挿入する。return answer;}template <typename T> inline T F( const T& t ){ return f<T>[t]; }template <typename T> inline T G( const int& i ){ return g<T>[i]; }ll Naive( int N , int M , int K ){ll answer = N + M + K;return answer;}ll Answer( ll N , ll M , ll K ){// START_WATCH;ll answer = N + M + K;// // TLに準じる乱択や全探索。デフォルトの猶予は100.0[ms]。// CEXPR( double , TL , 2000.0 );// while( CHECK_WATCH( TL ) ){// }return answer;}inline void Experiment(){// CEXPR( int , bound , 10 );// FOREQ( N , 0 , bound ){// FOREQ( M , 0 , bound ){// FOREQ( K , 0 , bound ){// COUT( N , M , K , ":" , Naive( N , M , K ) );// }// }// // cout << Naive( N ) << ",\n"[N==bound];// }}inline void SmallTest(){// CEXPR( int , bound , 10 );// FOREQ( N , 0 , bound ){// FOREQ( M , 0 , bound ){// FOREQ( K , 0 , bound ){// COMPARE( N , M , K );// }// }// // COMPARE( N );// }}#define INCLUDE_MAIN#include __FILE__#else // INCLUDE_SUB#ifdef INCLUDE_LIBRARY/*C-x 3 C-x o C-x C-fによるファイル操作用BFS:c:/Users/user/Documents/Programming/Mathematics/Geometry/Graph/BreadthFirstSearch/compress.txtCoordinateCompress:c:/Users/user/Documents/Programming/Mathematics/SetTheory/DirectProduct/CoordinateCompress/compress.txtDFSOnTreec:/Users/user/Documents/Programming/Mathematics/Geometry/Graph/DepthFirstSearch/Tree/a.hppDivisor:c:/Users/user/Documents/Programming/Mathematics/Arithmetic/Prime/Divisor/compress.txtPolynomialc:/Users/user/Documents/Programming/Mathematics/Polynomial/compress.txtUnionFindc:/Users/user/Documents/Programming/Utility/VLTree/UnionFindForest/compress.txt*/// VVV 常設でないライブラリは以下に挿入する。// Tが加法について可換群をなす場合にのみサポート。// - 構築 O(size)// - 一点根取得 O(α(size))// - 全根取得 O(rootの個数)// - 根数取得 O(1)// - 二点符号付き重み取得 O(α(size))// - 二点接合 O(α(size))template <typename T = int>class UnionFindForest{private:uint m_node_size;uint m_root_size;vector<uint> m_pred;vector<uint> m_length;// m_left_root[0]は左端のrootvector<uint> m_left_root;// m_right_root[m_size-1]は右端のrootvector<uint> m_right_root;// m_w[num]はnum番目のnodeがrootならば0、rootでないならば親nodeへ向かうパスの符号付き重みvector<T> m_w;public:UnionFindForest( const uint& size );// num番目のnodeのrootを計算して返す。const uint& RootOfNode( const uint& num );// rootを全て格納する。template <template <typename...> typename V> void SetRoot( V<uint>& a ) const;// num1番目のnodeからnum0番目のnodeへ向かうパスの符号付き重みを返す。inline T Weight( const uint& num0 , const uint& num1 );inline const uint& SizeOfNode() const noexcept;inline const uint& SizeOfRoot() const noexcept;// num0番目のnodeとnum1番目のnodeを符号付き重みwの有向辺num0->num1で結んだグラフと// 同等な連結性を持つようにそれぞれのrootを接合。void Graft( const uint& num0 , const uint& num1 , const T& w = 0 );};template <typename T>UnionFindForest<T>::UnionFindForest( const uint& size ) : m_node_size( size ) , m_root_size( m_node_size ) , m_pred( m_node_size ) , m_length(m_node_size , 1 ) , m_left_root( m_node_size ) , m_right_root( m_node_size ) , m_w( m_node_size ){for( uint i = 0 ; i < m_node_size ; i++ ){m_pred[i] = i;m_left_root[i] = i == 0 ? 0 : i - 1;m_right_root[i] = i + 1 == m_node_size ? i : i + 1;}}template <typename T>const uint& UnionFindForest<T>::RootOfNode( const uint& num ){uint& pred1 = m_pred[num];while( true ){uint& pred2 = m_pred[pred1];if( pred1 == pred2 ){break;}m_w[num] += m_w[pred1] += m_w[pred2];pred1 = pred2 = m_pred[pred2];}return pred1;}template <typename T> template <template <typename...> typename V>void UnionFindForest<T>::SetRoot( V<uint>& a ) const{a.clear();uint i = m_left_root[0];while( true ){a.push_back( i );if( i == m_right_root[i] ){break;}i = m_right_root[i];}return;}template <typename T>T UnionFindForest<T>::Weight( const uint& num0 , const uint& num1 ){assert( num0 < m_node_size && num1 < m_node_size );const uint& root0 = RootOfNode( num0 );const uint& root1 = RootOfNode( num1 );assert( root0 == root1 );return m_w[num1] - m_w[num0];}template <typename T> inline const uint& UnionFindForest<T>::SizeOfNode() const noexcept { return m_node_size; }template <typename T> inline const uint& UnionFindForest<T>::SizeOfRoot() const noexcept { return m_root_size; }template <typename T>void UnionFindForest<T>::Graft( const uint& num0 , const uint& num1 , const T& w ){const uint& root0 = RootOfNode( num0 );const uint& root1 = RootOfNode( num1 );if( root0 == root1 ){return;}uint& length0 = m_length[root0];const uint& length1 = m_length[root1];const uint* p_removed_root;const uint* p_removed_node;const uint* p_kept_root;if( length0 < length1 ){p_removed_root = &root0;p_removed_node = &num0;p_kept_root = &root1;m_w[root0] += w;} else {if( length0 == length1 ){length0++;}p_removed_root = &root1;p_removed_node = &num1;p_kept_root = &root0;m_w[root1] -= w;}const uint& left = m_left_root[*p_removed_root];const uint& right = m_right_root[*p_removed_root];if( left == *p_removed_root ){m_left_root[0] = m_left_root[right] = right;} else if( *p_removed_root == right ){m_right_root[m_node_size - 1] = m_right_root[left] = left;} else {m_left_root[right] = left;m_right_root[left] = right;}m_pred[*p_removed_node] = m_pred[*p_removed_root] = *p_kept_root;m_root_size--;return;}// AAA 常設でないライブラリは以上に挿入する。#define INCLUDE_SUB#include __FILE__#else // INCLUDE_LIBRARY// #define REACTIVE// #define USE_GETLINE#ifdef DEBUG#define _GLIBCXX_DEBUG#define REPEAT_MAIN( BOUND ) START_MAIN; signal( SIGABRT , &AlertAbort ); AutoCheck( exec_mode , use_getline ); if( exec_mode == sample_debug_mode ||exec_mode == submission_debug_mode || exec_mode == library_search_mode ){ return 0; } else if( exec_mode == experiment_mode ){ Experiment();return 0; } else if( exec_mode == small_test_mode ){ SmallTest(); return 0; }; DEXPR( int , bound_test_case_num , BOUND , min( BOUND , 100 ) );int test_case_num = 1; if( exec_mode == solve_mode ){ if constexpr( bound_test_case_num > 1 ){ SET_ASSERT( test_case_num , 1 ,bound_test_case_num ); } } else if( exec_mode == random_test_mode ){ CERR( "ランダムテストを行う回数を指定してください。" ); SET_LL(test_case_num ); } FINISH_MAIN#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 SET_ASSERT( A , MIN , MAX ) if( exec_mode == solve_mode ){ SET_LL( A ); ASSERT( A , MIN , MAX ); } else if( exec_mode == random_test_mode){ CERR( #A , " = " , ( A = GetRand( MIN , MAX ) ) ); } else { assert( false ); }#define SOLVE_ONLY static_assert( __FUNCTION__[0] == 'S' )#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 REPEAT_MAIN( BOUND ) START_MAIN; CEXPR( int , bound_test_case_num , BOUND ); int test_case_num = 1; if constexpr( bound_test_case_num > 1){ SET_ASSERT( test_case_num , 1 , bound_test_case_num ); } FINISH_MAIN#define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE )#define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )#define SET_ASSERT( A , MIN , MAX ) SET_LL( A ); ASSERT( A , MIN , MAX )#define SOLVE_ONLY#define CERR( ... )#define COUT( ... ) VariadicCout( cout , __VA_ARGS__ ) << ENDL#define CERR_A( A , N )#define COUT_A( A , N ) OUTPUT_ARRAY( cout , A , N ) << ENDL#define CERR_ITR( A )#define COUT_ITR( A ) OUTPUT_ITR( cout , A ) << ENDL#endif#ifdef REACTIVE#define ENDL endl#else#define ENDL "\n"#endif#ifdef USE_GETLINE#define SET_LL( A ) { GETLINE( A ## _str ); A = stoll( A_str ); }#define GETLINE_SEPARATE( SEPARATOR , ... ) SOLVE_ONLY; string __VA_ARGS__; VariadicGetline( cin , SEPARATOR , __VA_ARGS__ )#define GETLINE( ... ) SOLVE_ONLY; GETLINE_SEPARATE( '\n' , __VA_ARGS__ )#else#define SET_LL( A ) cin >> A#define CIN( LL , ... ) SOLVE_ONLY; LL __VA_ARGS__; VariadicCin( cin , __VA_ARGS__ )#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 );#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>;using path = pair<int,ll>;#define ATT __attribute__( ( target( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) ) )#define START_MAIN int main(){ ios_base::sync_with_stdio( false ); cin.tie( nullptr )#define FINISH_MAIN REPEAT( test_case_num ){ if constexpr( bound_test_case_num > 1 ){ CERR( "testcase " , VARIABLE_FOR_REPEAT_test_case_num , ":" );} Solve(); CERR( "" ); } }#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_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 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( ... ) SOLVE_ONLY; COUT( __VA_ARGS__ ); return#define COMPARE( ... ) auto naive = Naive( __VA_ARGS__ ); auto answer = Answer( __VA_ARGS__ ); bool match = naive == answer; COUT( #__VA_ARGS__ , ":", naive , match ? "==" : "!=" , answer ); if( !match ){ 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 , constchar& 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; }const string direction[4] = {"U","R","D","L"};// (i,j)->(k,h)の方向番号を取得inline int DirectionNumberOnGrid( const int& i , const int& j , const int& k , const int& h ){return i<k?2:i>k?0:j<h?1:j>h?3:(assert(false),-1);}// v->wの方向番号を取得inline int DirectionNumberOnGrid( const int& v , const int& w ){auto [i,j]=EnumHW(v);auto [k,h]=EnumHW(w);return DirectionNumberOnGrid(i,j,k,h);}// 方向番号の反転U<->D、R<->Linline int ReverseDirectionNumberOnGrid( const int& n ){assert(0<=n&&n<4);return(n+2)%4;}inline void SetEdgeOnGrid( const string& Si , const int& i , list<int> ( &e )[] , const char& walkable = '.' ){FOR(j,0,W){if(Si[j]==walkable){int v =EnumHW_inv(i,j);if(i>0){e[EnumHW_inv(i-1,j)].push_back(v);}if(i+1<H){e[EnumHW_inv(i+1,j)].push_back(v);}if(j>0){e[EnumHW_inv(i,j-1)].push_back(v);}if(j+1<W){e[EnumHW_inv(i,j+1)].push_back(v);}}}}inline void SetEdgeOnGrid( const string& Si , const int& i , list<path> ( &e )[] , const char& walkable = '.' ){FOR(j,0,W){if(Si[j]==walkable){constint v=EnumHW_inv(i,j);if(i>0){e[EnumHW_inv(i-1,j)].push_back({v,1});}if(i+1<H){e[EnumHW_inv(i+1,j)].push_back({v,1});}if(j>0){e[EnumHW_inv(i,j-1)].push_back({v,1});}if(j+1<W){e[EnumHW_inv(i,j+1)].push_back({v,1});}}}}inline void SetWallOnGrid( const string& Si , const int& i , vector<vector<bool> >& non_wall , const char& walkable = '.' , const char& unwalkable ='#' ){non_wall.push_back(vector<bool>(W));auto& non_wall_i=non_wall[i];FOR(j,0,W){non_wall_i[j]=Si[j]==walkable?true:(assert(Si[j]==unwalkable),false);}}// グラフ用template <typename PATH> vector<list<PATH> > e;template <typename T> map<T,T> f;template <typename T> vector<T> g;// デバッグ用#ifdef DEBUGinline void AlertAbort( int n ) { CERR("abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); }void AutoCheck( int& exec_mode , const bool& use_getline );inline void Solve();inline void Experiment();inline void SmallTest();inline void RandomTest();ll GetRand( const ll& Rand_min , const ll& Rand_max );int exec_mode;CEXPR( int , solve_mode , 0 );CEXPR( int , sample_debug_mode , 1 );CEXPR( int , submission_debug_mode , 2 );CEXPR( int , library_search_mode , 3 );CEXPR( int , experiment_mode , 4 );CEXPR( int , small_test_mode , 5 );CEXPR( int , random_test_mode , 6 );#ifdef USE_GETLINECEXPR( bool , use_getline , true );#elseCEXPR( bool , use_getline , false );#endif#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&// VVV 常設ライブラリは以下に挿入する。// AAA 常設ライブラリは以上に挿入する。#define INCLUDE_LIBRARY#include __FILE__#endif // INCLUDE_LIBRARY#endif // INCLUDE_SUB#endif // INCLUDE_MAIN