結果
| 問題 | No.2160 みたりのDominator |
| コンテスト | |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2024-04-25 13:18:49 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 627 ms / 2,000 ms |
| コード長 | 11,284 bytes |
| コンパイル時間 | 3,015 ms |
| コンパイル使用メモリ | 224,072 KB |
| 最終ジャッジ日時 | 2025-02-21 08:54:18 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 93 |
ソースコード
// #define _GLIBCXX_DEBUG
#pragma GCC optimize ( "O3" )
//#pragma GCC target ( "avx" )
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
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 GETLINE( A ) string A; getline( cin , A )
#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR )
#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
#define DOUBLE( PRECISION , ANSWER ) cout << fixed << setprecision( PRECISION ) << ( ANSWER ) << "\n"; QUIT
#define POWER( ANSWER , ARGUMENT , EXPONENT ) \
TYPE_OF( ARGUMENT ) ANSWER{ 1 }; \
{ \
TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT ); \
TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \
while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \
if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \
ANSWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \
} \
ARGUMENT_FOR_SQUARE_FOR_POWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \
EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \
} \
} \
#define POWER_MOD( ANSWER , ARGUMENT , EXPONENT , MODULO ) \
TYPE_OF( ARGUMENT ) ANSWER{ 1 }; \
{ \
TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( MODULO + ( ARGUMENT ) % MODULO ) % MODULO; \
TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \
while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \
if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \
ANSWER = ( ANSWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \
} \
ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT_FOR_SQUARE_FOR_POWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \
EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \
} \
} \
#define FACTORIAL_MOD( ANSWER , ANSWER_INV , MAX_I , LENGTH , MODULO ) \
ll ANSWER[LENGTH]; \
ll ANSWER_INV[LENGTH]; \
{ \
ll VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1; \
ANSWER[0] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL; \
FOREQ( i , 1 , MAX_I ){ \
ANSWER[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= i ) %= MODULO; \
} \
POWER_MOD( FACTORIAL_MAX_INV , ANSWER[MAX_I] , MODULO - 2 , MODULO ); \
ANSWER_INV[MAX_I] = FACTORIAL_MAX_INV; \
FOREQINV( i , MAX_I - 1 , 0 ){ \
ANSWER_INV[i] = ( FACTORIAL_MAX_INV *= i + 1 ) %= MODULO; \
} \
} \
\
// 通常の二分探索
#define BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
ll ANSWER = MAXIMUM; \
{ \
ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM; \
ll VARIABLE_FOR_BINARY_SEARCH_U = ANSWER; \
ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( TARGET ) - ( EXPRESSION ); \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \
VARIABLE_FOR_BINARY_SEARCH_L = ANSWER; \
} else { \
ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
} \
while( VARIABLE_FOR_BINARY_SEARCH_L != ANSWER ){ \
VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( TARGET ) - ( EXPRESSION ); \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \
VARIABLE_FOR_BINARY_SEARCH_L = ANSWER; \
break; \
} else { \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH > 0 ){ \
VARIABLE_FOR_BINARY_SEARCH_L = ANSWER; \
} else { \
VARIABLE_FOR_BINARY_SEARCH_U = ANSWER; \
} \
ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
} \
} \
} \
\
// 二進法の二分探索
#define BS2( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
ll ANSWER = MINIMUM; \
{ \
ll VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 = 1; \
ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( MAXIMUM ) - ANSWER; \
while( VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 <= VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ){ \
VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 *= 2; \
} \
VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 /= 2; \
ll VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 = ANSWER; \
while( VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 != 0 ){ \
ANSWER = VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 + VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2; \
VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( TARGET ) - ( EXPRESSION ); \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \
VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 = ANSWER; \
break; \
} else if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH > 0 ){ \
VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2 = ANSWER; \
} \
VARIABLE_FOR_POWER_FOR_BINARY_SEARCH_2 /= 2; \
} \
ANSWER = VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH_2; \
} \
\
template <typename T> inline T Absolute( const T& a ){ return a > 0 ? a : - a; }
template <typename T> inline T Residue( const T& a , const T& p ){ return a >= 0 ? a % p : p - ( - a - 1 ) % p - 1; }
class DirectedGraph
{
public:
int m_N;
vector<vector<int> > m_e;
inline DirectedGraph( int N ) : m_N( N ) , m_e( m_N ) {}
inline void AddEdge( int i , int j ) { m_e[i].push_back( j ); }
};
int main()
{
UNTIE;
CIN( int , N1 );
CIN( int , N2 );
CIN( int , N3 );
int N12 = N1 + N2;
int N123 = N12 + N3;
CEXPR( int , bound_N123 , 300000 );
assert( 0 <= N1 && 0 <= N2 && 0 <= N2 && N123 <= bound_N123 );
CEXPR( int , bound_t , bound_N123 + 2 );
int s = N123 + 1;
int t = s + 1;
int startpoint[4] = { 1 , N1 + 1 , N12 + 1 , s };
int endpoint[4] = { N1 , N12 , N123 , t };
int sp_curr , ep_curr;
DirectedGraph G{ t + 1 };
DirectedGraph G_inv{ t + 1 };
FOR( line , 0 , 3 ){
sp_curr = startpoint[line];
ep_curr = endpoint[line];
G.AddEdge( s , sp_curr );
G_inv.AddEdge( sp_curr , s );
FOR( i , sp_curr , ep_curr ){
G.AddEdge( i , i + 1 );
G_inv.AddEdge( i + 1 , i );
}
G.AddEdge( ep_curr , t );
G_inv.AddEdge( t , ep_curr );
}
CIN_ASSERT( M , 0 , bound_N123 );
FOR( i , 0 , M ){
CIN_ASSERT( Ui , 1 , t );
CIN_ASSERT( Vi , 1 , t );
G.AddEdge( Ui , Vi );
G.AddEdge( Vi , Ui );
G_inv.AddEdge( Ui , Vi );
G_inv.AddEdge( Vi , Ui );
}
static bool used[bound_t + 1] = {};
used[0] = true;
int count = 0;
vector<int> path{};
vector<vector<int> > branch{};
vector<int>* p_branch_end;
DirectedGraph* p_G = &G;
int u , v;
int enumv[bound_t];
while( count < t ){
u = 1;
while( used[u] ){
u++;
}
used[u] = true;
path.push_back( u );
branch.push_back( p_G->m_e[u] );
while( ! branch.empty() ){
u = path.back();
p_branch_end = &( branch.back() );
while( ! p_branch_end->empty() ? used[v = p_branch_end->back()] : false ){
p_branch_end->pop_back();
}
if( p_branch_end->empty() ){
enumv[count] = u;
count++;
path.pop_back();
branch.pop_back();
} else {
used[v] = true;
p_branch_end->pop_back();
path.push_back( v );
branch.push_back( p_G->m_e[v] );
}
}
}
u = 0;
while( ++u <= t ){
used[u] = false;
}
count = 0;
static int scc[bound_t];
int scc_count = 0;
p_G = &G_inv;
int u_start = t - 1;
while( count < t ){
FOREQINV( i , u_start , 0 ){
u = enumv[i];
if( ! used[u] ){
u_start = i - 1;
break;
}
}
used[u] = true;
path.push_back( u );
branch.push_back( p_G->m_e[u] );
while( ! branch.empty() ){
u = path.back();
p_branch_end = &( branch.back() );
while( ! p_branch_end->empty() ? used[v = p_branch_end->back()] : false ){
p_branch_end->pop_back();
}
if( p_branch_end->empty() ){
scc[u] = scc_count;
count++;
path.pop_back();
branch.pop_back();
} else {
used[v] = true;
p_branch_end->pop_back();
path.push_back( v );
branch.push_back( p_G->m_e[v] );
}
}
scc_count++;
}
DirectedGraph Gscc{ scc_count };
DirectedGraph Gscc_inv{ scc_count };
int sccu , sccv;
FOR( line , 0 , 3 ){
sp_curr = startpoint[line];
ep_curr = endpoint[line];
sccu = scc[s];
sccv = scc[sp_curr];
if( sccu != sccv ){
Gscc.AddEdge( sccu , sccv );
Gscc_inv.AddEdge( sccv , sccu );
}
FOR( i , sp_curr , ep_curr ){
sccu = scc[i];
sccv = scc[i+1];
if( sccu != sccv ){
Gscc.AddEdge( sccu , sccv );
Gscc_inv.AddEdge( sccv , sccu );
}
}
sccu = scc[ep_curr];
sccv = scc[t];
if( sccu != sccv ){
Gscc.AddEdge( sccu , sccv );
Gscc_inv.AddEdge( sccv , sccu );
}
}
FOR( i , 0 , scc_count ){
used[i] = false;
}
int red_count = 0;
static int redc[bound_t];
static int redc_inv[bound_t];
FOR( i , 0 , scc_count ){
vector<int>& eu = Gscc.m_e[i];
vector<int>& eu_inv = Gscc_inv.m_e[i];
if( eu.size() != 1 || eu_inv.size() != 1 ){
redc[red_count] = i;
redc_inv[i] = red_count;
red_count++;
}
}
DirectedGraph Gred( red_count );
static vector<int> length[bound_t];
int eu_size , redc_inv_i , pvk;
vector<int> *pv , *pv_inv;
FOR( i , 0 , scc_count ){
vector<int>& eu = Gscc.m_e[i];
vector<int>& eu_inv = Gscc_inv.m_e[i];
eu_size = eu.size();
if( eu_size != 1 || eu_inv.size() != 1 ){
redc_inv_i = redc_inv[i];
vector<int>& length_i = length[redc_inv_i];
length_i = vector<int>( eu_size , 1 );
FOR( k , 0 , eu_size ){
pvk = eu[k];
pv = &( Gscc.m_e[pvk] );
pv_inv = &( Gscc_inv.m_e[pvk] );
int& length_i_k = length_i[k];
while( pv->size() == 1 && pv_inv->size() == 1 ){
used[pvk] = true;
pvk = ( *pv )[0];
pv = &( Gscc.m_e[pvk] );
pv_inv = &( Gscc_inv.m_e[pvk] );
length_i_k++;
}
Gred.AddEdge( redc_inv_i , redc_inv[pvk] );
}
}
}
static ll line_comb[bound_t];
FOR( i , 0 , red_count ){
line_comb[i] = 1;
}
line_comb[redc_inv[scc[t]]] = 0;
int euv , length_u_v;
FOR( i , 0 , red_count ){
u = redc[i];
vector<int>& length_u = length[i];
vector<int>& eu = Gred.m_e[i];
eu_size = eu.size();
FOR( j , 0 , eu_size ){
euv = eu[j];
length_u_v = length_u[j];
FOR( k , i , euv ){
line_comb[k] *= length_u_v;
}
}
}
ll answer = 0;
FOR( i , 0 , red_count ){
answer += line_comb[i];
}
RETURN( answer );
}