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

• 問題: No.2536 同値性と充足可能性
• ユーザー: 👑 p-adic
• 提出日時: 2024-01-02 09:53:03
• 言語: C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 40 ms / 2,000 ms
• コード長: 6,013 bytes
• コンパイル時間: 10,959 ms
• コンパイル使用メモリ: 280,036 KB
• 最終ジャッジ日時: 2025-02-18 15:51:40
• ジャッジサーバーID （参考情報）: judge5 / judge1

ファイルパターン	結果
other	AC * 31

コンパイルメッセージ

main.cpp: In function 'int main()':
main.cpp:76:28: warning: narrowing conversion of '(N * 2)' from 'std::decay_t<const int>' {aka 'int'} to 'uint' {aka 'unsigned int'} [-Wnarrowing]
   76 |   UnionFindForest<> uff{ N * 2 };
      |                          ~~^~~

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#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
// 圧縮用
#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&
TE <TY T = int>CL UnionFindForest{PU:uint m_node_SZ;uint m_root_SZ;VE<uint> m_pred;VE<uint> m_height;VE<T> m_w;IN UnionFindForest(CRUI SZ);CRUI 
    RootOfNode(CRUI num);TE <TE <TY...> TY V> VO SetRoot(V<uint>& a)CO;IN T Weight(CRUI num0,CRUI num1);IN CRUI SZOfNode()CO NE;IN CRUI SZOfRoot()CO 
    NE;bool Graft(CRUI num0,CRUI num1,CO T& w = 0);};
TE <TY T> IN UnionFindForest<T>::UnionFindForest(CRUI SZ):m_node_SZ(SZ),m_root_SZ(m_node_SZ),m_pred(m_node_SZ),m_height(m_node_SZ,1),m_w(m_node_SZ
    ){for(uint i = 0;i < m_node_SZ;i++){m_pred[i]= i;}}TE <TY T>CRUI UnionFindForest<T>::RootOfNode(CRUI num){uint& pred1 = m_pred[num];WH(true
    ){uint& pred2 = m_pred[pred1];if(pred1 == pred2){break;}m_w[num]+= m_w[pred1]+= m_w[pred2];pred1 = pred2 = m_pred[pred2];}RE pred1;}TE <TY T> TE 
    <TE <TY...> TY V>VO UnionFindForest<T>::SetRoot(V<uint>& a)CO{a.clear();for(uint i = 0;i < m_node_SZ;i++){if(i == m_pred[i]){a.push_back(i);}}RE
    ;}TE <TY T>T UnionFindForest<T>::Weight(CRUI num0,CRUI num1){assert(num0 < m_node_SZ && num1 < m_node_SZ);CRUI root0 = RootOfNode(num0);CRUI 
    root1 = RootOfNode(num1);assert(root0 == root1);RE m_w[num1]- m_w[num0];}TE <TY T> IN CRUI UnionFindForest<T>::SZOfNode()CO NE{RE m_node_SZ;}TE 
    <TY T> IN CRUI UnionFindForest<T>::SZOfRoot()CO NE{RE m_root_SZ;}TE <TY T>bool UnionFindForest<T>::Graft(CRUI num0,CRUI num1,CO T& w){assert(num0 
    < m_node_SZ && num1 < m_node_SZ);CRUI root0 = RootOfNode(num0);CRUI root1 = RootOfNode(num1);if(root0 == root1){RE Weight(num0,num1)== w;}uint& 
    height0 = m_height[root0];CRUI height1 = m_height[root1];CO uint* p_reMOd_root;CO uint* p_reMOd_node;CO uint* p_kept_root;if(height0 < height1
    ){p_reMOd_root = &root0;p_reMOd_node = &num0;p_kept_root = &root1;m_w[*p_reMOd_root]-= w - m_w[num1]+ m_w[num0];}else{if(height0 == height1
    ){height0++;}p_reMOd_root = &root1;p_reMOd_node = &num1;p_kept_root = &root0;m_w[*p_reMOd_root]+= w - m_w[num1]+ m_w[num0];}if(*p_reMOd_node != 
    *p_reMOd_root){m_w[*p_reMOd_node]+= m_w[*p_reMOd_root];}m_pred[*p_reMOd_node]= m_pred[*p_reMOd_root]= *p_kept_root;m_root_SZ--;RE 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;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX