結果

問題 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
// Resetm_foundm_prev
// Shiftm_foundm_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 );
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0