結果
| 問題 | No.2536 同値性と充足可能性 |
| コンテスト | |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2023-08-13 17:29:29 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 204 ms / 2,000 ms |
| コード長 | 9,314 bytes |
| 記録 | |
| コンパイル時間 | 11,302 ms |
| コンパイル使用メモリ | 278,888 KB |
| 最終ジャッジ日時 | 2025-02-16 07:52:47 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 31 |
ソースコード
#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;
}