#903717 (C++17) No.2536 同値性と充足可能性

• 問題: No.2536 同値性と充足可能性
• ユーザー: 👑 p-adic
• 提出日時: 2023-08-13 17:29:29
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 136 ms / 2,000 ms
• コード長: 9,314 bytes
• コンパイル時間: 3,087 ms
• コンパイル使用メモリ: 223,288 KB
• 実行使用メモリ: 23,784 KB
• 最終ジャッジ日時: 2024-05-08 02:38:12
• 合計ジャッジ時間: 6,422 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	6 ms; 9,808 KB
testcase_01	AC	6 ms; 9,836 KB
testcase_02	AC	5 ms; 9,776 KB
testcase_03	AC	5 ms; 9,752 KB
testcase_04	AC	5 ms; 9,796 KB
testcase_05	AC	6 ms; 9,976 KB
testcase_06	AC	6 ms; 9,912 KB
testcase_07	AC	6 ms; 9,760 KB
testcase_08	AC	6 ms; 9,760 KB
testcase_09	AC	5 ms; 9,904 KB
testcase_10	AC	5 ms; 9,916 KB
testcase_11	AC	4 ms; 9,784 KB
testcase_12	AC	6 ms; 10,004 KB
testcase_13	AC	4 ms; 9,872 KB
testcase_14	AC	5 ms; 9,920 KB
testcase_15	AC	4 ms; 9,900 KB
testcase_16	AC	5 ms; 9,788 KB
testcase_17	AC	6 ms; 10,096 KB
testcase_18	AC	6 ms; 10,024 KB
testcase_19	AC	6 ms; 9,888 KB
testcase_20	AC	12 ms; 11,088 KB
testcase_21	AC	11 ms; 11,212 KB
testcase_22	AC	12 ms; 11,268 KB
testcase_23	AC	91 ms; 22,828 KB
testcase_24	AC	88 ms; 22,768 KB
testcase_25	AC	136 ms; 23,584 KB
testcase_26	AC	122 ms; 23,624 KB
testcase_27	AC	119 ms; 23,784 KB
testcase_28	AC	131 ms; 23,612 KB
testcase_29	AC	119 ms; 23,704 KB
testcase_30	AC	122 ms; 23,472 KB

ソースコード

#ifdef DEBUG
  #define _GLIBCXX_DEBUG
  #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ); signal( SIGABRT , &AlertAbort )
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , DEBUG_VALUE )
  #define CERR( MESSAGE ) cerr << MESSAGE << endl;
  #define COUT( ANSWER ) cout << ANSWER << endl
  #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック： " << ( MIN ) << ( ( MIN ) <= A ? "<=" : ">" ) << A << ( A <= ( MAX ) ? "<=" : ">" ) << ( MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) )
#else
  #pragma GCC optimize ( "O3" )
  #pragma GCC optimize( "unroll-loops" )
  #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
  #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr )
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE )
  #define CERR( MESSAGE ) 
  #define COUT( ANSWER ) cout << ANSWER << "\n"
  #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
#endif
#include <bits/stdc++.h>
using namespace std;
#define MAIN main
#define TYPE_OF( VAR ) decay_t<decltype( VAR )>
#define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE
#define CIN( LL , A ) LL A; cin >> A
#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 QUIT return 0
#define SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX )
#define RETURN( ANSWER ) COUT( ( ANSWER ) ); QUIT

#ifdef DEBUG
  inline void AlertAbort( int n ) { CERR( "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); }
#endif

// 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_numx )[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 = 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 );

inline DEXPR( int , bound_N , 100000 , 100 ); // 0が5個
TYPE_OF( bound_N ) N;
inline DEXPR( int , bound_M , 100000 , 100 ); // 0が5個
TYPE_OF( bound_M ) M;

list<int> e[bound_N*2];
inline list<int> E( const int& i ) { return e[i]; }

int MAIN()
{
  UNTIE;

  SET_ASSERT( N , 2 , bound_N );
  SET_ASSERT( M , 1 , bound_M );
  assert( M / ( N - 1 ) <= N );

  string equiv[2] = { "<==>" , "<=/=>" };
  
  FOR( m , 0 , M ){
    CIN_ASSERT( i , 1 , N );
    CIN( string , E );
    CIN_ASSERT( j , i + 1 , N );
    i--;
    j--;
    int b = E == equiv[0] ? 0 : ( assert( E == equiv[1] ) , 1 );
    e[i].push_back( j + b * N );
    e[j + b * N].push_back( i );
    e[i + N].push_back( j + ( 1 - b ) * N );
    e[j + ( 1 - b ) * N].push_back( i + N );
  }

  int connected_component_num[bound_N*2];
  int total_connected_component_num;
  BreadthFirstConnectedComponentSearch<bound_N*2,E>( N * 2 , connected_component_num , total_connected_component_num );

  int count_chosen = 0;
  int chosen_connected_component_num[bound_N*2] = {};
  FOR( i , 0 , N ){
    int& connected_component_num_i = connected_component_num[i];
    int& connected_component_num_i_N = connected_component_num[i + N];
    if( connected_component_num_i == connected_component_num_i_N ){
      RETURN( "No" );
    }
    int& chosen_connected_component_num_i = chosen_connected_component_num[connected_component_num_i];
    if( chosen_connected_component_num_i == 0 ){
      chosen_connected_component_num_i = 1;
      chosen_connected_component_num[connected_component_num_i_N] = 2;
    }
    if( chosen_connected_component_num_i == 1 ){
      count_chosen++;
    }
  }

  bool non_flip;
  if( count_chosen * 2 >= N ){
    non_flip = true;
  } else {
    non_flip = false;
    count_chosen = N - count_chosen;
  }
  COUT( "Yes" );
  COUT( count_chosen );

  FOR( i , 0 , N ){
    int& connected_component_num_i = connected_component_num[i];
    if( ( chosen_connected_component_num[connected_component_num_i] == 1 ) == non_flip ){
      cout << i + 1 << " \n"[--count_chosen==0];
    }
  }
  QUIT;
}