#941705 (C++17(gcc12)) No.2914 正閉路検出

提出ソース
結果

問題	No.2914 正閉路検出
コンテスト
ユーザー	👑 p-adic
提出日時	2024-01-03 11:01:58
言語	C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
結果	WA
実行時間	-
コード長	17,824 bytes
コンパイル時間	15,104 ms
コンパイル使用メモリ	296,012 KB
最終ジャッジ日時	2025-02-18 15:59:46
ジャッジサーバーID （参考情報）	judge4 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 52 WA * 3
権限があれば一括ダウンロードができます
ソースコード

raw source code
// 誤解法（オーバーフロー）チェックその１
#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;
      int 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
yukicoder

結果

ソースコード
