結果
| 問題 | No.2536 同値性と充足可能性 |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2024-01-02 09:17:50 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 40 ms / 2,000 ms |
| コード長 | 7,793 bytes |
| コンパイル時間 | 11,433 ms |
| コンパイル使用メモリ | 279,208 KB |
| 最終ジャッジ日時 | 2025-02-18 15:50:59 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 31 |
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:231:28: warning: narrowing conversion of '(N * 2)' from 'std::decay_t<const int>' {aka 'int'} to 'uint' {aka 'unsigned int'} [-Wnarrowing]
231 | UnionFindForest<> uff{ N * 2 };
| ~~^~~
ソースコード
#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 DEBUGinline void AlertAbort( int n ) { CERR("abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); }#endif// 圧縮用#define TE template#define TY typename#define US using#define ST static#define IN inline#define CL class#define PU public#define OP operator#define CE constexpr#define CO const#define NE noexcept#define RE return#define WH while#define VO void#define VE vector#define LI list#define BE begin#define EN end#define SZ size#define MO move#define TH this#define CRI CO int&#define CRUI CO uint&#define CRL CO ll&// 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;}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;int MAIN(){UNTIE;SET_ASSERT( N , 2 , bound_N );SET_ASSERT( M , 1 , bound_M );assert( M / ( N - 1 ) <= N );UnionFindForest<> uff{ N * 2 };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 );uff.Graft( i , j + b * N );uff.Graft( i + N , j + ( 1 - b ) * N );}int count_chosen = 0;int chosen_connected_component_num[bound_N*2] = {};FOR( i , 0 , N ){const int& connected_component_num_i = uff.RootOfNode( i );const int& connected_component_num_i_N = uff.RootOfNode( 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 ){const int& connected_component_num_i = uff.RootOfNode( i );if( ( chosen_connected_component_num[connected_component_num_i] == 1 ) == non_flip ){cout << i + 1 << " \n"[--count_chosen==0];}}QUIT;}