結果
| 問題 | No.3491 右結合的総乗 |
| コンテスト | |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2023-09-10 16:39:38 |
| 言語 | C++17(gcc12) (gcc 12.4.0 + boost 1.89.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 8,515 bytes |
| 記録 | |
| コンパイル時間 | 2,166 ms |
| コンパイル使用メモリ | 228,240 KB |
| 実行使用メモリ | 320,256 KB |
| 最終ジャッジ日時 | 2026-04-03 20:50:48 |
| 合計ジャッジ時間 | 11,737 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 24 MLE * 16 |
ソースコード
// 誤解法（空間計算量O(NM)解）チェック
#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 SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX )
#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 FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ )
#define AUTO_ITR( ARRAY ) auto itr_ ## ARRAY = ARRAY .begin() , end_ ## ARRAY = ARRAY .end()
#define FOR_ITR( ARRAY ) for( AUTO_ITR( ARRAY ) , itr = itr_ ## ARRAY ; itr_ ## ARRAY != end_ ## ARRAY ; itr_ ## ARRAY ++ , itr++ )
#define QUIT return 0
#define RETURN( ANSWER ) COUT( ( ANSWER ) ); QUIT
#ifdef DEBUG
inline void AlertAbort( int n ) { CERR( "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); }
#endif
// Resetはm_foundとm_prevを初期化
// Shiftはm_foundとm_prevを非初期化
// Breadth/DepthFirstConnectedComponentSearchは無向グラフの連結成分を色分け＆数え上げ
// Next()の反復でm_initから到達可能な頂点を全探索。
// 計算量O((m_initの連結成分)+(m_initの連結成分におけるEのサイズの合計))
#define DECLARATION_OF_FIRST_SEARCH( BREADTH ) \
template <int V_max> \
class BREADTH ## FirstSearch_Body \
{ \
\
protected: \
int m_V; \
int m_init; \
list<int> m_next; \
bool m_found[V_max]; \
int m_prev[V_max]; \
\
public: \
inline BREADTH ## FirstSearch_Body( const int& V ); \
inline BREADTH ## FirstSearch_Body( const int& V , const int& init ); \
\
inline void Reset( const int& init ); \
inline void Shift( const int& init ); \
\
inline const int& size() const; \
inline const int& init() const; \
inline bool& found( const int& i ); \
inline const int& prev( const int& i ) const; \
\
int Next(); \
\
private: \
virtual list<int> e( const int& t ) = 0; \
\
}; \
\
template <int V_max,list<int> E(const int&)> \
class BREADTH ## FirstSearch : \
public BREADTH ## FirstSearch_Body<V_max> \
{ \
\
public: \
\
template<typename... Args> inline BREADTH ## FirstSearch( const Args&... args ); \
\
private: \
inline list<int> e( const int& t ); \
\
}; \
\
template <int V_max,list<int> E(const int&)> void BREADTH ## FirstConnectedComponentSearch( const int& V , int ( &cc_numx )[V_max] , int& count ); \
#define DEFINITION_OF_FIRST_SEARCH( BREADTH , PUSH ) \
template <int V_max> inline BREADTH ## FirstSearch_Body<V_max>::BREADTH ## FirstSearch_Body( const int& V ) : m_V( V ) , m_init() , m_next() , m_found() , m_prev() { assert( m_V <= V_max ); for( int i = 0 ; i < m_V ; i++ ){ m_prev[i] = -1; } } \
template <int V_max> inline BREADTH ## FirstSearch_Body<V_max>::BREADTH ## FirstSearch_Body( const int& V , const int& init ) : BREADTH ## FirstSearch_Body( V ) { m_init = init; m_next.push_back( m_init ); m_found[m_init] = true; } \
template <int V_max,list<int> E(const int&)> template <typename... Args> inline BREADTH ## FirstSearch<V_max,E>::BREADTH ## FirstSearch( const Args&... args ) : BREADTH ## FirstSearch_Body<V_max>( args... ) {} \
\
template <int V_max> inline void BREADTH ## FirstSearch_Body<V_max>::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> inline void BREADTH ## FirstSearch_Body<V_max>::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> inline const int& BREADTH ## FirstSearch_Body<V_max>::size() const { return m_V; } \
template <int V_max> inline const int& BREADTH ## FirstSearch_Body<V_max>::init() const { return m_init; } \
template <int V_max> inline bool& BREADTH ## FirstSearch_Body<V_max>::found( const int& i ) { assert( i < m_V ); return m_found[i]; } \
template <int V_max> inline const int& BREADTH ## FirstSearch_Body<V_max>::prev( const int& i ) const { assert( i < m_V ); return m_prev[i]; } \
\
template <int V_max> \
int BREADTH ## FirstSearch_Body<V_max>::Next() \
{ \
\
if( m_next.empty() ){ \
\
return -1; \
\
} \
\
const int i_curr = m_next.front(); \
m_next.pop_front(); \
list<int> edge = e( i_curr ); \
\
while( ! edge.empty() ){ \
\
const int& i = edge.front(); \
bool& found_i = found( i ); \
\
if( ! found_i ){ \
\
m_next.PUSH( i ); \
m_prev[i] = i_curr; \
found_i = true; \
\
} \
\
edge.pop_front(); \
\
} \
\
return i_curr; \
\
} \
\
template <int V_max,list<int> E(const int&)> inline list <int> BREADTH ## FirstSearch<V_max,E>::e( const int& t ) { return E( t ); } \
\
template <int V_max,list<int> E(const int&)> void BREADTH ## FirstConnectedComponentSearch( const int& V , int ( &cc_num )[V_max] , int& count ) \
{ \
\
BREADTH ## FirstSearch<V_max,E> bfs{ V }; \
count = 0; \
\
for( int i = 0 ; i < V ; i++ ){ \
\
cc_num[i] = -1; \
\
} \
\
for( int i = 0 ; i < V ; i++ ){ \
\
if( cc_num[i] == -1 ){ \
\
bfs.Shift( i ); \
int j = bfs.Next(); \
\
while( j != -1 ? cc_num[j] == -1 : false ){ \
\
cc_num[j] = count; \
j = bfs.Next(); \
\
} \
\
count++; \
\
} \
\
} \
\
return; \
\
} \
DECLARATION_OF_FIRST_SEARCH( Breadth );
DEFINITION_OF_FIRST_SEARCH( Breadth , push_back );
inline DEXPR( int , bound_N , 4000 , 100 ); // 0が3個
list<int> e[bound_N+2] = {};
list<int> E( const int& j ) { return e[j]; }
int MAIN()
{
UNTIE;
CIN_ASSERT( N , 0 , bound_N );
CIN_ASSERT( M , 1 , N + 1 );
int A[bound_N*2+1];
int N2 = N * 2;
FOREQ( k , 0 , N2 ){
CIN_ASSERT( Ak , 0 , N );
A[k] = Ak;
}
list<int> S{};
FOR( m , 0 , M ){
CIN( int , sm );
S.push_back( sm );
}
FOREQ( j , 0 , N ){
bool found[bound_N+1] = {};
FOR_ITR( S ){
found[A[ *itr + j]] = true;
}
auto& e_j = e[j];
FOREQ( k , 0 , N ){
if( found[k] ){
e_j.push_back( k );
}
}
}
int init = N+1;
auto& e_init = e[init];
FOR_ITR( S ){
e_init.push_back( *itr );
}
BreadthFirstSearch<bound_N+2,E> bfs{ init + 1 , init };
int answer = -1;
while( bfs.Next() != -1 ){
answer++;
}
RETURN( answer );
}