結果
問題 | No.2205 Lights Out on Christmas Tree |
ユーザー | 👑 p-adic |
提出日時 | 2023-05-31 20:55:06 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 135 ms / 2,000 ms |
コード長 | 5,283 bytes |
コンパイル時間 | 4,190 ms |
コンパイル使用メモリ | 218,724 KB |
実行使用メモリ | 34,368 KB |
最終ジャッジ日時 | 2023-08-28 01:38:17 |
合計ジャッジ時間 | 10,207 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
9,048 KB |
testcase_01 | AC | 5 ms
9,120 KB |
testcase_02 | AC | 5 ms
9,240 KB |
testcase_03 | AC | 5 ms
9,020 KB |
testcase_04 | AC | 6 ms
9,032 KB |
testcase_05 | AC | 6 ms
9,028 KB |
testcase_06 | AC | 6 ms
9,040 KB |
testcase_07 | AC | 6 ms
9,248 KB |
testcase_08 | AC | 6 ms
9,012 KB |
testcase_09 | AC | 6 ms
9,092 KB |
testcase_10 | AC | 5 ms
9,048 KB |
testcase_11 | AC | 113 ms
34,232 KB |
testcase_12 | AC | 115 ms
34,368 KB |
testcase_13 | AC | 112 ms
34,236 KB |
testcase_14 | AC | 107 ms
34,220 KB |
testcase_15 | AC | 105 ms
27,996 KB |
testcase_16 | AC | 76 ms
21,528 KB |
testcase_17 | AC | 73 ms
21,460 KB |
testcase_18 | AC | 5 ms
9,028 KB |
testcase_19 | AC | 117 ms
28,268 KB |
testcase_20 | AC | 124 ms
27,984 KB |
testcase_21 | AC | 125 ms
27,992 KB |
testcase_22 | AC | 108 ms
28,188 KB |
testcase_23 | AC | 116 ms
27,996 KB |
testcase_24 | AC | 118 ms
27,992 KB |
testcase_25 | AC | 128 ms
28,096 KB |
testcase_26 | AC | 133 ms
27,964 KB |
testcase_27 | AC | 116 ms
27,948 KB |
testcase_28 | AC | 106 ms
27,972 KB |
testcase_29 | AC | 111 ms
27,996 KB |
testcase_30 | AC | 133 ms
28,120 KB |
testcase_31 | AC | 118 ms
28,152 KB |
testcase_32 | AC | 118 ms
27,940 KB |
testcase_33 | AC | 118 ms
27,976 KB |
testcase_34 | AC | 115 ms
27,984 KB |
testcase_35 | AC | 132 ms
27,992 KB |
testcase_36 | AC | 131 ms
27,992 KB |
testcase_37 | AC | 117 ms
28,044 KB |
testcase_38 | AC | 135 ms
27,976 KB |
testcase_39 | AC | 115 ms
27,960 KB |
ソースコード
#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 ); }