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

提出ソース

結果

問題	No.2160 みたりのDominator
ユーザー	👑 p-adic
提出日時	2024-04-25 13:18:49
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	570 ms / 2,000 ms
コード長	11,284 bytes
コンパイル時間	2,816 ms
コンパイル使用メモリ	219,800 KB
実行使用メモリ	89,108 KB
最終ジャッジ日時	2024-04-25 13:19:13
合計ジャッジ時間	20,781 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	5 ms 12,648 KB
testcase_01	AC	139 ms 83,364 KB
testcase_02	AC	6 ms 12,640 KB
testcase_03	AC	6 ms 13,932 KB
testcase_04	AC	6 ms 13,844 KB
testcase_05	AC	5 ms 12,588 KB
testcase_06	AC	5 ms 12,564 KB
testcase_07	AC	6 ms 13,360 KB
testcase_08	AC	6 ms 12,704 KB
testcase_09	AC	5 ms 12,580 KB
testcase_10	AC	5 ms 12,752 KB
testcase_11	AC	6 ms 12,876 KB
testcase_12	AC	5 ms 13,524 KB
testcase_13	AC	5 ms 13,028 KB
testcase_14	AC	5 ms 12,616 KB
testcase_15	AC	5 ms 12,664 KB
testcase_16	AC	6 ms 12,660 KB
testcase_17	AC	5 ms 12,768 KB
testcase_18	AC	4 ms 13,504 KB
testcase_19	AC	6 ms 12,560 KB
testcase_20	AC	4 ms 14,132 KB
testcase_21	AC	6 ms 13,524 KB
testcase_22	AC	6 ms 12,664 KB
testcase_23	AC	6 ms 12,612 KB
testcase_24	AC	5 ms 12,636 KB
testcase_25	AC	6 ms 12,740 KB
testcase_26	AC	6 ms 12,924 KB
testcase_27	AC	6 ms 13,408 KB
testcase_28	AC	6 ms 13,312 KB
testcase_29	AC	5 ms 14,228 KB
testcase_30	AC	6 ms 13,236 KB
testcase_31	AC	6 ms 13,196 KB
testcase_32	AC	5 ms 12,584 KB
testcase_33	AC	6 ms 13,260 KB
testcase_34	AC	164 ms 89,108 KB
testcase_35	AC	6 ms 13,012 KB
testcase_36	AC	6 ms 12,380 KB
testcase_37	AC	6 ms 12,712 KB
testcase_38	AC	5 ms 13,508 KB
testcase_39	AC	5 ms 12,628 KB
testcase_40	AC	200 ms 79,196 KB
testcase_41	AC	183 ms 78,752 KB
testcase_42	AC	107 ms 51,296 KB
testcase_43	AC	153 ms 62,716 KB
testcase_44	AC	199 ms 76,744 KB
testcase_45	AC	189 ms 68,496 KB
testcase_46	AC	161 ms 63,832 KB
testcase_47	AC	91 ms 39,416 KB
testcase_48	AC	114 ms 43,296 KB
testcase_49	AC	149 ms 48,680 KB
testcase_50	AC	157 ms 49,000 KB
testcase_51	AC	129 ms 56,700 KB
testcase_52	AC	176 ms 72,876 KB
testcase_53	AC	200 ms 75,880 KB
testcase_54	AC	117 ms 49,236 KB
testcase_55	AC	453 ms 47,948 KB
testcase_56	AC	272 ms 42,736 KB
testcase_57	AC	342 ms 43,532 KB
testcase_58	AC	496 ms 54,728 KB
testcase_59	AC	351 ms 46,400 KB
testcase_60	AC	214 ms 55,032 KB
testcase_61	AC	425 ms 45,392 KB
testcase_62	AC	570 ms 58,048 KB
testcase_63	AC	458 ms 48,912 KB
testcase_64	AC	174 ms 47,176 KB
testcase_65	AC	251 ms 42,036 KB
testcase_66	AC	266 ms 38,088 KB
testcase_67	AC	274 ms 39,736 KB
testcase_68	AC	562 ms 54,680 KB
testcase_69	AC	376 ms 43,528 KB
testcase_70	AC	535 ms 56,656 KB
testcase_71	AC	200 ms 39,320 KB
testcase_72	AC	404 ms 54,976 KB
testcase_73	AC	520 ms 47,720 KB
testcase_74	AC	474 ms 45,728 KB
testcase_75	AC	62 ms 41,572 KB
testcase_76	AC	51 ms 35,064 KB
testcase_77	AC	320 ms 55,168 KB
testcase_78	AC	377 ms 55,560 KB
testcase_79	AC	40 ms 27,056 KB
testcase_80	AC	48 ms 29,716 KB
testcase_81	AC	83 ms 47,268 KB
testcase_82	AC	94 ms 48,380 KB
testcase_83	AC	139 ms 46,252 KB
61_evil_bias_nocross_01.txt	AC	202 ms 81,216 KB
61_evil_bias_nocross_02.txt	AC	189 ms 78,700 KB
61_evil_bias_nocross_03.txt	AC	107 ms 52,428 KB
61_evil_bias_nocross_04.txt	AC	143 ms 63,304 KB
61_evil_bias_nocross_05.txt	AC	189 ms 78,056 KB
61_evil_bias_nocross_06.txt	AC	196 ms 79,240 KB
61_evil_bias_nocross_07.txt	AC	130 ms 56,944 KB
61_evil_bias_nocross_08.txt	AC	171 ms 72,900 KB
61_evil_bias_nocross_09.txt	AC	172 ms 76,400 KB
61_evil_bias_nocross_10.txt	AC	102 ms 50,196 KB
61_evil_bias_nocross_11.txt	AC	146 ms 61,516 KB
61_evil_bias_nocross_12.txt	AC	178 ms 69,732 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

結果

テストケース

ソースコード