結果
問題 | 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_MAINinline 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_SUBtemplate <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( constArgs&... 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 , constchar& 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 DEBUGinline 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