結果

問題 No.2914 正閉路検出
ユーザー 👑 p-adicp-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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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]numnoderoot0rootnode
vector<T> m_w;
public:
inline UnionFindForest( const uint& size );
// numnoderoot
const uint& RootOfNode( const uint& num );
// root
template <template <typename...> typename V> void SetRoot( V<uint>& a ) const;
// num1nodenum0node
inline T Weight( const uint& num0 , const uint& num1 );
inline const uint& SizeOfNode() const noexcept;
inline const uint& SizeOfRoot() const noexcept;
// num1nodenum0nodew
// rootfalse
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;
}
// Resetm_foundm_prev
// Shiftm_foundm_prev
// Breadth/DepthFirstConnectedComponentSearch
// Next()m_init
// O((m_init)+(m_initE))
#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(
      "abortassert" ); }
void AutoCheck( bool& auto_checked );
#endif
#define INCLUDE_LIBRARY
#include __FILE__
#endif // INCLUDE_LIBRARY
#endif // INCLUDE_SUB
#endif // INCLUDE_MAIN
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0