#825310 (C++17) No.2160 みたりのDominator

提出ソース

結果

問題	No.2160 みたりのDominator
ユーザー	👑 p-adic
提出日時	2022-12-13 02:54:30
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	575 ms / 2,000 ms
コード長	11,282 bytes
コンパイル時間	4,043 ms
コンパイル使用メモリ	228,520 KB
実行使用メモリ	89,696 KB
最終ジャッジ日時	2024-04-27 04:23:16
合計ジャッジ時間	21,478 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	6 ms 12,284 KB
testcase_01	AC	154 ms 83,124 KB
testcase_02	AC	6 ms 12,648 KB
testcase_03	AC	6 ms 13,564 KB
testcase_04	AC	5 ms 13,852 KB
testcase_05	AC	6 ms 12,780 KB
testcase_06	AC	7 ms 13,300 KB
testcase_07	AC	8 ms 12,632 KB
testcase_08	AC	5 ms 14,164 KB
testcase_09	AC	6 ms 14,020 KB
testcase_10	AC	7 ms 12,856 KB
testcase_11	AC	5 ms 14,048 KB
testcase_12	AC	5 ms 12,560 KB
testcase_13	AC	5 ms 12,408 KB
testcase_14	AC	6 ms 12,476 KB
testcase_15	AC	7 ms 13,172 KB
testcase_16	AC	6 ms 13,320 KB
testcase_17	AC	5 ms 13,976 KB
testcase_18	AC	7 ms 12,696 KB
testcase_19	AC	6 ms 12,936 KB
testcase_20	AC	6 ms 12,624 KB
testcase_21	AC	7 ms 12,980 KB
testcase_22	AC	6 ms 13,384 KB
testcase_23	AC	6 ms 12,532 KB
testcase_24	AC	7 ms 12,792 KB
testcase_25	AC	7 ms 12,592 KB
testcase_26	AC	6 ms 12,988 KB
testcase_27	AC	6 ms 12,496 KB
testcase_28	AC	6 ms 13,652 KB
testcase_29	AC	6 ms 13,024 KB
testcase_30	AC	5 ms 13,600 KB
testcase_31	AC	6 ms 13,852 KB
testcase_32	AC	5 ms 12,444 KB
testcase_33	AC	6 ms 12,908 KB
testcase_34	AC	165 ms 89,696 KB
testcase_35	AC	7 ms 12,412 KB
testcase_36	AC	8 ms 12,940 KB
testcase_37	AC	5 ms 14,108 KB
testcase_38	AC	7 ms 13,460 KB
testcase_39	AC	5 ms 12,628 KB
testcase_40	AC	222 ms 79,208 KB
testcase_41	AC	206 ms 78,316 KB
testcase_42	AC	123 ms 51,260 KB
testcase_43	AC	173 ms 62,932 KB
testcase_44	AC	216 ms 76,764 KB
testcase_45	AC	206 ms 68,960 KB
testcase_46	AC	174 ms 62,952 KB
testcase_47	AC	103 ms 39,412 KB
testcase_48	AC	129 ms 43,304 KB
testcase_49	AC	159 ms 48,768 KB
testcase_50	AC	156 ms 49,376 KB
testcase_51	AC	136 ms 57,028 KB
testcase_52	AC	192 ms 73,012 KB
testcase_53	AC	219 ms 76,192 KB
testcase_54	AC	123 ms 51,308 KB
testcase_55	AC	491 ms 47,700 KB
testcase_56	AC	331 ms 42,856 KB
testcase_57	AC	452 ms 43,656 KB
testcase_58	AC	498 ms 54,736 KB
testcase_59	AC	424 ms 46,752 KB
testcase_60	AC	230 ms 55,148 KB
testcase_61	AC	458 ms 46,312 KB
testcase_62	AC	554 ms 58,180 KB
testcase_63	AC	493 ms 48,788 KB
testcase_64	AC	180 ms 46,808 KB
testcase_65	AC	249 ms 42,008 KB
testcase_66	AC	263 ms 37,204 KB
testcase_67	AC	293 ms 39,592 KB
testcase_68	AC	573 ms 54,928 KB
testcase_69	AC	386 ms 43,824 KB
testcase_70	AC	575 ms 55,984 KB
testcase_71	AC	214 ms 39,364 KB
testcase_72	AC	424 ms 55,080 KB
testcase_73	AC	546 ms 48,412 KB
testcase_74	AC	515 ms 46,156 KB
testcase_75	AC	67 ms 40,524 KB
testcase_76	AC	55 ms 34,988 KB
testcase_77	AC	335 ms 55,228 KB
testcase_78	AC	392 ms 55,604 KB
testcase_79	AC	41 ms 26,840 KB
testcase_80	AC	51 ms 29,976 KB
testcase_81	AC	87 ms 46,864 KB
testcase_82	AC	103 ms 47,984 KB
testcase_83	AC	134 ms 46,804 KB
61_evil_bias_nocross_01.txt	AC	217 ms 79,268 KB
61_evil_bias_nocross_02.txt	AC	201 ms 78,624 KB
61_evil_bias_nocross_03.txt	AC	111 ms 52,276 KB
61_evil_bias_nocross_04.txt	AC	158 ms 63,464 KB
61_evil_bias_nocross_05.txt	AC	201 ms 78,548 KB
61_evil_bias_nocross_06.txt	AC	217 ms 78,752 KB
61_evil_bias_nocross_07.txt	AC	137 ms 56,080 KB
61_evil_bias_nocross_08.txt	AC	188 ms 72,640 KB
61_evil_bias_nocross_09.txt	AC	191 ms 76,568 KB
61_evil_bias_nocross_10.txt	AC	114 ms 49,932 KB
61_evil_bias_nocross_11.txt	AC	144 ms 61,340 KB
61_evil_bias_nocross_12.txt	AC	190 ms 69,528 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

yukicoder

結果

テストケース

ソースコード