結果
問題 | No.2205 Lights Out on Christmas Tree |
ユーザー |
👑 |
提出日時 | 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 |
ソースコード
#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 ); returnm_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 );}