結果

問題 No.2160 みたりのDominator
ユーザー 👑 p-adicp-adic
提出日時 2024-04-25 13:18:49
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 581 ms / 2,000 ms
コード長 11,284 bytes
コンパイル時間 2,822 ms
コンパイル使用メモリ 224,032 KB
実行使用メモリ 86,692 KB
最終ジャッジ日時 2024-11-08 00:22:58
合計ジャッジ時間 22,425 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
10,368 KB
testcase_01 AC 176 ms
81,124 KB
testcase_02 AC 8 ms
10,368 KB
testcase_03 AC 8 ms
10,624 KB
testcase_04 AC 8 ms
10,496 KB
testcase_05 AC 8 ms
10,624 KB
testcase_06 AC 8 ms
10,496 KB
testcase_07 AC 8 ms
10,496 KB
testcase_08 AC 8 ms
10,624 KB
testcase_09 AC 8 ms
10,496 KB
testcase_10 AC 8 ms
10,496 KB
testcase_11 AC 8 ms
10,624 KB
testcase_12 AC 8 ms
10,496 KB
testcase_13 AC 8 ms
10,624 KB
testcase_14 AC 8 ms
10,496 KB
testcase_15 AC 8 ms
10,496 KB
testcase_16 AC 9 ms
10,496 KB
testcase_17 AC 7 ms
10,624 KB
testcase_18 AC 8 ms
10,624 KB
testcase_19 AC 8 ms
10,624 KB
testcase_20 AC 8 ms
10,496 KB
testcase_21 AC 8 ms
10,496 KB
testcase_22 AC 8 ms
10,496 KB
testcase_23 AC 9 ms
10,496 KB
testcase_24 AC 8 ms
10,496 KB
testcase_25 AC 8 ms
10,496 KB
testcase_26 AC 8 ms
10,496 KB
testcase_27 AC 8 ms
10,496 KB
testcase_28 AC 9 ms
10,624 KB
testcase_29 AC 8 ms
10,496 KB
testcase_30 AC 8 ms
10,496 KB
testcase_31 AC 9 ms
10,624 KB
testcase_32 AC 8 ms
10,624 KB
testcase_33 AC 8 ms
10,496 KB
testcase_34 AC 174 ms
86,692 KB
testcase_35 AC 8 ms
10,368 KB
testcase_36 AC 9 ms
10,368 KB
testcase_37 AC 9 ms
10,496 KB
testcase_38 AC 8 ms
10,368 KB
testcase_39 AC 8 ms
10,368 KB
testcase_40 AC 231 ms
77,960 KB
testcase_41 AC 212 ms
77,196 KB
testcase_42 AC 130 ms
50,068 KB
testcase_43 AC 177 ms
61,296 KB
testcase_44 AC 224 ms
75,656 KB
testcase_45 AC 211 ms
67,252 KB
testcase_46 AC 183 ms
60,876 KB
testcase_47 AC 104 ms
37,104 KB
testcase_48 AC 136 ms
41,064 KB
testcase_49 AC 164 ms
46,628 KB
testcase_50 AC 160 ms
46,932 KB
testcase_51 AC 145 ms
55,008 KB
testcase_52 AC 200 ms
71,664 KB
testcase_53 AC 221 ms
74,932 KB
testcase_54 AC 125 ms
47,776 KB
testcase_55 AC 483 ms
45,148 KB
testcase_56 AC 285 ms
40,376 KB
testcase_57 AC 369 ms
41,288 KB
testcase_58 AC 499 ms
52,372 KB
testcase_59 AC 430 ms
44,380 KB
testcase_60 AC 239 ms
52,736 KB
testcase_61 AC 469 ms
43,400 KB
testcase_62 AC 572 ms
55,844 KB
testcase_63 AC 504 ms
46,424 KB
testcase_64 AC 186 ms
44,672 KB
testcase_65 AC 267 ms
39,560 KB
testcase_66 AC 277 ms
35,084 KB
testcase_67 AC 295 ms
36,316 KB
testcase_68 AC 574 ms
52,188 KB
testcase_69 AC 395 ms
41,460 KB
testcase_70 AC 581 ms
53,340 KB
testcase_71 AC 210 ms
37,228 KB
testcase_72 AC 419 ms
52,556 KB
testcase_73 AC 539 ms
46,028 KB
testcase_74 AC 510 ms
43,796 KB
testcase_75 AC 70 ms
38,568 KB
testcase_76 AC 59 ms
32,740 KB
testcase_77 AC 342 ms
52,760 KB
testcase_78 AC 405 ms
53,376 KB
testcase_79 AC 45 ms
24,636 KB
testcase_80 AC 53 ms
27,580 KB
testcase_81 AC 92 ms
44,528 KB
testcase_82 AC 105 ms
45,656 KB
testcase_83 AC 136 ms
44,388 KB
61_evil_bias_nocross_01.txt AC 225 ms
77,964 KB
61_evil_bias_nocross_02.txt AC 211 ms
77,320 KB
61_evil_bias_nocross_03.txt AC 120 ms
50,008 KB
61_evil_bias_nocross_04.txt AC 162 ms
61,364 KB
61_evil_bias_nocross_05.txt AC 208 ms
75,668 KB
61_evil_bias_nocross_06.txt AC 220 ms
77,956 KB
61_evil_bias_nocross_07.txt AC 143 ms
55,008 KB
61_evil_bias_nocross_08.txt AC 194 ms
71,540 KB
61_evil_bias_nocross_09.txt AC 199 ms
75,000 KB
61_evil_bias_nocross_10.txt AC 118 ms
47,840 KB
61_evil_bias_nocross_11.txt AC 152 ms
60,164 KB
61_evil_bias_nocross_12.txt AC 198 ms
68,124 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #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 );
}
0