結果
問題 | No.2914 正閉路検出 |
ユーザー | 👑 p-adic |
提出日時 | 2024-01-02 17:51:14 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 318 ms / 2,000 ms |
コード長 | 17,742 bytes |
コンパイル時間 | 4,295 ms |
コンパイル使用メモリ | 239,240 KB |
実行使用メモリ | 37,200 KB |
最終ジャッジ日時 | 2024-07-19 18:48:35 |
合計ジャッジ時間 | 14,764 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 3 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 3 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 3 ms
5,376 KB |
testcase_11 | AC | 3 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 3 ms
5,376 KB |
testcase_14 | AC | 3 ms
5,376 KB |
testcase_15 | AC | 3 ms
5,376 KB |
testcase_16 | AC | 3 ms
5,376 KB |
testcase_17 | AC | 3 ms
5,376 KB |
testcase_18 | AC | 3 ms
5,376 KB |
testcase_19 | AC | 29 ms
7,808 KB |
testcase_20 | AC | 57 ms
13,184 KB |
testcase_21 | AC | 14 ms
6,016 KB |
testcase_22 | AC | 66 ms
15,104 KB |
testcase_23 | AC | 55 ms
12,416 KB |
testcase_24 | AC | 91 ms
17,408 KB |
testcase_25 | AC | 7 ms
5,376 KB |
testcase_26 | AC | 12 ms
5,888 KB |
testcase_27 | AC | 143 ms
17,408 KB |
testcase_28 | AC | 207 ms
19,200 KB |
testcase_29 | AC | 211 ms
34,484 KB |
testcase_30 | AC | 25 ms
15,872 KB |
testcase_31 | AC | 173 ms
18,048 KB |
testcase_32 | AC | 242 ms
19,768 KB |
testcase_33 | AC | 28 ms
16,288 KB |
testcase_34 | AC | 318 ms
35,456 KB |
testcase_35 | AC | 229 ms
35,456 KB |
testcase_36 | AC | 262 ms
35,548 KB |
testcase_37 | AC | 108 ms
37,200 KB |
testcase_38 | AC | 84 ms
36,096 KB |
testcase_39 | AC | 103 ms
25,664 KB |
testcase_40 | AC | 191 ms
35,696 KB |
testcase_41 | AC | 126 ms
29,056 KB |
testcase_42 | AC | 181 ms
36,608 KB |
testcase_43 | AC | 186 ms
35,672 KB |
testcase_44 | AC | 98 ms
25,148 KB |
testcase_45 | AC | 167 ms
34,228 KB |
testcase_46 | AC | 162 ms
33,660 KB |
testcase_47 | AC | 154 ms
32,396 KB |
testcase_48 | AC | 115 ms
26,688 KB |
testcase_49 | AC | 179 ms
34,944 KB |
testcase_50 | AC | 152 ms
32,384 KB |
testcase_51 | AC | 98 ms
36,016 KB |
testcase_52 | AC | 85 ms
36,480 KB |
testcase_53 | AC | 95 ms
36,608 KB |
testcase_54 | AC | 97 ms
36,480 KB |
ソースコード
#ifndef INCLUDE_MODE #define INCLUDE_MODE // #define REACTIVE // #define USE_GETLINE #endif #ifdef INCLUDE_MAIN inline void Solve() { DEXPR( int , bound , 1e5 , 10 ); CIN_ASSERT( N , 2 , bound ); CIN_ASSERT( M , 1 , bound ); gE<int>.resize( N ); UnionFindForest<ll> uff{ uint( N ) }; unordered_map<int,T2<int>> W[N]; FOR( j , 0 , M ){ CIN_ASSERT( uj , 1 , N ); CIN_ASSERT( vj , 1 , N ); assert( --uj != --vj ); CIN_ASSERT( wj , 0 , bound ); if( uff.Graft( uj , vj , -wj ) ){ gE<int>[uj].push_back( vj ); gE<int>[vj].push_back( uj ); W[uj][vj] = {wj,j}; W[vj][uj] = {-wj,j}; } else { BreadthFirstSearch<bound,GetgE<int>> bfs{ N , uj }; while( bfs.Next() != vj ){} vector<int> answer{}; answer.push_back( j + 1 ); ll w = wj; while( uj != vj ){ int uk = bfs.prev( vj ); auto& [wk,k] = W[vj][uk]; answer.push_back( k + 1 ); w += wk; vj = uk; } assert( w != 0 ); int L = answer.size(); COUT( L ); COUT( ++uj ); if( w > 0 ){ COUT_A( answer , L ); } else { FOREQINV( i , L-1 , 0 ){ cout << answer[i] << " \n"[i==0]; } } return; } } RETURN( -1 ); } REPEAT_MAIN(1); #else // INCLUDE_MAIN #ifdef INCLUDE_SUB template <typename PATH> list<PATH> GetgE( const int& i ) { // list<PATH> answer{}; list<PATH> answer = gE<PATH>[i]; // VVV 入力によらない処理は以下に挿入する。 // AAA 入力によらない処理は以上に挿入する。 return answer; } #define INCLUDE_MAIN #include __FILE__ #else // INCLUDE_SUB #ifdef INCLUDE_LIBRARY // https://github.com/p-adic/cpp // VVV ライブラリは以下に挿入する。 // Tが加法について可換群をなす場合にのみサポート。 // - 構築 O(size) // - 一点根取得 O(α(size)) // - 全根取得 O(size) // - 根数取得 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_height; // m_w[num]はnum番目のnodeがrootならば0、rootでないならば親nodeへ向かうパスの符号付き重み vector<T> m_w; public: inline 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; // num1番目のnodeからnum0番目のnodeへ符号付き重みwの有向辺を結ぶ操作と整合的に // なるようにrootを接合。符号付き重みの整合性が取れない場合はfalseを返す。 bool Graft( const uint& num0 , const uint& num1 , const T& w = 0 ); }; template <typename T> inline UnionFindForest<T>::UnionFindForest( const uint& size ) : m_node_size( size ) , m_root_size( m_node_size ) , m_pred( m_node_size ) , m_height( m_node_size , 1 ) , m_w( m_node_size ) { for( uint i = 0 ; i < m_node_size ; i++ ){ m_pred[i] = i; } } 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(); for( uint i = 0 ; i < m_node_size ; i++ ){ if( i == m_pred[i] ){ a.push_back( 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> bool UnionFindForest<T>::Graft( const uint& num0 , const uint& num1 , const T& w ) { assert( num0 < m_node_size && num1 < m_node_size ); const uint& root0 = RootOfNode( num0 ); const uint& root1 = RootOfNode( num1 ); if( root0 == root1 ){ return Weight( num0 , num1 ) == w; } uint& height0 = m_height[root0]; const uint& height1 = m_height[root1]; const uint* p_removed_root; const uint* p_removed_node; const uint* p_kept_root; if( height0 < height1 ){ p_removed_root = &root0; p_removed_node = &num0; p_kept_root = &root1; m_w[*p_removed_root] -= w - m_w[num1] + m_w[num0]; } else { if( height0 == height1 ){ height0++; } p_removed_root = &root1; p_removed_node = &num1; p_kept_root = &root0; m_w[*p_removed_root] += w - m_w[num1] + m_w[num0]; } if( *p_removed_node != *p_removed_root ){ m_w[*p_removed_node] += m_w[*p_removed_root]; } m_pred[*p_removed_node] = m_pred[*p_removed_root] = *p_kept_root; m_root_size--; return true; } // 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_num )[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 ); // AAA ライブラリは以上に挿入する。 #define INCLUDE_SUB #include __FILE__ #else // INCLUDE_LIBRARY #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__ ) << 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 , ... ) string __VA_ARGS__; VariadicGetline( cin , SEPARATOR , __VA_ARGS__ ) #define GETLINE( ... ) GETLINE_SEPARATE( '\n' , __VA_ARGS__ ) #else #define SET_LL( A ) cin >> A #define CIN( LL , ... ) LL __VA_ARGS__; VariadicCin( cin , __VA_ARGS__ ) #define SET_A( A , N ) 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>; #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 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 SET_ASSERT( A , MIN , MAX ) SET_LL( 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 + 1 > 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>& operator<<( basic_ostream<char,Traits>& os , const vector<Arg>& arg ) { auto begin = arg.begin() , end = arg.end(); auto itr = begin; while( itr != end ){ ( itr == begin ? os : os << " " ) << *itr; itr++; } return os; } 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... ); } // グラフ用 template <typename PATH> vector<list<PATH> > gE; // デバッグ用 #ifdef DEBUG inline void AlertAbort( int n ) { CERR( "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); } void AutoCheck( bool& auto_checked ); #endif #define INCLUDE_LIBRARY #include __FILE__ #endif // INCLUDE_LIBRARY #endif // INCLUDE_SUB #endif // INCLUDE_MAIN