結果

問題 No.2205 Lights Out on Christmas Tree
コンテスト
ユーザー 👑 p-adic
提出日時 2023-05-31 20:55:06
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 155 ms / 2,000 ms
コード長 5,283 bytes
コンパイル時間 10,610 ms
コンパイル使用メモリ 277,628 KB
最終ジャッジ日時 2025-02-13 17:06:35
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef DEBUG
  #define _GLIBCXX_DEBUG
#else
  #pragma GCC optimize ( "O3" )
  #pragma GCC optimize( "unroll-loops" )
  #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::type >::type
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr )
#define CEXPR( LL , BOUND , VALUE ) constexpr const LL BOUND = VALUE
#define CIN( LL , A ) LL A; cin >> A
#define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
#define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); 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 >= FINAL ; VAR -- )
#define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES )
#define QUIT return 0
#define COUT( ANSWER ) cout << ( ANSWER ) << "\n"
#define RETURN( ANSWER ) COUT( ANSWER ); QUIT

// Resetはm_foundとm_prevも初期化
// Shiftはm_foundとm_prevは非初期化
#define DECLARATION_OF_FIRST_SEARCH( BREADTH )				\
  template <int V_max,list<int> E(const int&)>				\
  class BREADTH ## FirstSearch						\
  {									\
									\
  private:								\
    int m_V;								\
    int m_init;								\
    list<int> m_next;							\
    bool m_found[V_max];						\
    int m_prev[V_max];							\
									\
  public:								\
    inline BREADTH ## FirstSearch( const int& V );			\
    inline BREADTH ## FirstSearch( const int& V , const int& init );	\
									\
    inline void Reset( const int& init );				\
    inline void Shift( const int& init );				\
									\
    bool& found( const int& i );					\
    const int& prev( const int& i ) const;				\
									\
    int Next();								\
									\
  };									\

#define DEFINITION_OF_FIRST_SEARCH( BREADTH , PUSH )			\
  template <int V_max,list<int> E(const int&)> inline BREADTH ## FirstSearch<V_max,E>::BREADTH ## FirstSearch( const int& V ) : m_V( V ) , m_init() , m_next() , m_found() , m_prev() { for( int i = 0 ; i < m_V ; i++ ){ m_prev[i] = -1; } } \
  template <int V_max,list<int> E(const int&)> inline BREADTH ## FirstSearch<V_max,E>::BREADTH ## FirstSearch( const int& V , const int& init ) : BREADTH ## FirstSearch( V ) { m_init = init; m_next.push_back( m_init ); m_found[m_init] = true; } \
									\
  template <int V_max,list<int> E(const int&)> inline void BREADTH ## FirstSearch<V_max,E>::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,list<int> E(const int&)> inline void BREADTH ## FirstSearch<V_max,E>::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,list<int> E(const int&)> inline bool& BREADTH ## FirstSearch<V_max,E>::found( const int& i ) { assert( i < m_V ); return m_found[i]; } \
  template <int V_max,list<int> E(const int&)> inline const int& BREADTH ## FirstSearch<V_max,E>::prev( const int& i ) const { assert( i < m_V ); return m_prev[i]; } \
									\
  template <int V_max,list<int> E(const int&)>				\
  int BREADTH ## FirstSearch<V_max,E>::Next()				\
  {									\
									\
    if( m_next.empty() ){						\
									\
      return -1;							\
									\
    }									\
									\
    const int i_curr = m_next.front();					\
    m_next.pop_front();							\
    list<int> edge = E( i_curr );					\
									\
    for( auto itr = edge.begin() , end = edge.end() ; itr != end ; itr++ ){ \
									\
      const int& i = *itr;						\
      bool& found_i = found( i );					\
									\
      if( ! found_i ){							\
									\
	m_next.PUSH( i );						\
	m_prev[i] = i_curr;						\
	found_i = true;							\
									\
      }									\
									\
    }									\
									\
    return i_curr;							\
									\
  }									\



DECLARATION_OF_FIRST_SEARCH( Depth );
DEFINITION_OF_FIRST_SEARCH( Depth , push_front );


inline CEXPR( int , bound_N , 200000 );
list<int> edge[bound_N] = {};

inline list<int> E( const int& i ) { return edge[i]; }

int main()
{
  UNTIE;
  CIN_ASSERT( N , 2 , bound_N );
  FOR( i , 1 , N ){
    CIN_ASSERT( a , 1 , N );
    CIN_ASSERT( b , a + 1 , N );
    a--;
    b--;
    edge[a].push_back( b );
    edge[b].push_back( a );
  }
  bool black[bound_N];
  FOR( i , 0 , N ){
    CIN_ASSERT( Ci , 0 , 1 );
    black[i] = Ci == 1;
  }
  DepthFirstSearch<bound_N,E> dfs{ N , 0 };
  list<int> node{};
  REPEAT( N ){
    node.push_front( dfs.Next() );
  }
  int answer = 0;
  FOR_ITR( node , itr , end ){
    int& i = *itr;
    if( ! black[i] ){
      answer++;
      if( i != 0 ){
	bool& black_i_prev = black[ dfs.prev( i ) ];
	black_i_prev = !black_i_prev;
      }
    }
  }
  RETURN( black[0] ? answer : -1 );
}
0