結果

問題 No.5007 Steiner Space Travel
ユーザー 👑 p-adicp-adic
提出日時 2022-08-23 02:23:22
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 14,421 bytes
コンパイル時間 1,786 ms
実行使用メモリ 12,220 KB
スコア 0
最終ジャッジ日時 2022-08-23 02:23:55
合計ジャッジ時間 26,701 ms
ジャッジサーバーID
(参考情報)
judge15 / judge12
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: 関数 ‘int main()’ 内:
main.cpp:10:78: 警告: ‘num_start’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
   10 | #define FOR_LL( VAR , INITIAL , FINAL_PLUS_ONE ) for( ll VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
      |                                                                              ^
main.cpp:416:6: 備考: ‘num_start’ はここで定義されています
  416 |   ll num_start;
      |      ^~~~~~~~~
main.cpp:412:43: 警告: ‘k_start’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
  412 |   ll& near_k_start_0 = near[PATH_min[k0]][PATH_min_start_1][1];
      |                                           ^~~~~~~~~~~~~~~~
main.cpp:469:30: 警告: ‘s_min’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
  469 |     while( m_size[PATH_min[k2]] == 0 ){
      |                   ~~~~~~~~~~~^
main.cpp:10:78: 警告: ‘path_length_00’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
   10 | #define FOR_LL( VAR , INITIAL , FINAL_PLUS_ONE ) for( ll VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
      |                                                                              ^
main.cpp:244:8: 備考: ‘path_length_00’ はここで定義されています
  244 |     ll path_length_00;
      |        ^~~~~~~~~~~~~~
main.cpp:261:11: 警告: ‘path_E_00’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
  261 |           if( computed_path_E_00 ? path_E_00 > path_E_current : true ){
      |           ^~
main.cpp:98:24: 警告: ‘m_kj_min’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
   98 |             near_kk[1] = m_kj_min;                              \
      |                        ^
main.cpp:83:14: 備

ソースコード

diff #

#include<bits/stdc++.h>
using namespace std;

using uint = unsigned int;
using ll = long long;

#define CIN( LL , A ) LL A; cin >> A 
#define GETLINE( A ) string A; getline( cin , A ) 
#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR ) 
#define FOR_LL( VAR , INITIAL , FINAL_PLUS_ONE ) for( ll VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) 
#define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ ) 
#define REPEAT( HOW_MANY_TIMES ) FOR_LL( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) 
#define RETURN( ANSWER ) cout << ( ANSWER ) << endl; return 0 
#define DOUBLE( PRECISION , ANSWER ) cout << fixed << setprecision( PRECISION ) << ( ANSWER ) << endl; return 0 
#define MIN( A , B ) A < B ? A : B;
#define MAX( A , B ) A < B ? B : A;
template <typename T> inline T Distance( const T& a , const T& b ){ return a < b ? b - a : a - b; }


#define SetAB( x , y )				\
						\
  a[num] = x;					\
  b[num] = y;					\
  ll p_num = ( x / W ) + ( y / H ) * Px;	\
  p[num] = p_num;				\
  ll& m_size_p_num = m_size[p_num];		\
  m[p_num][m_size_p_num] = num;			\
  m_size_p_num++;				\
						\



#define SetNear							\
								\
  P_valid = 0;							\
  FOR_LL( k , 0 , P ){						\
    if( m_size[k] > 0 ){					\
      k_valid[P_valid] = k;					\
      P_valid++;						\
    }								\
  }								\
  bool setting = true;						\
  while( setting ){						\
    FOR_LL( k , 0 , P_valid ){					\
      ll& k0 = k_valid[k];					\
      ll (&m_k)[NM] = m[k0];					\
      ll& m_size_k = m_size[k0];				\
      ll (&near_k)[P][2] = near[k0];				\
      ll (&E_min_k)[P] = E_min[k0];				\
      FOR_LL( h , 0 , k ){					\
	ll& k1 = k_valid[h];					\
	ll (&m_h)[NM] = m[k1];					\
	ll& m_size_h = m_size[k1];				\
	ll (&near_kh)[2] = near_k[k1];				\
	ll& E_min_kh = E_min_k[k1];				\
	E_min_kh = 50000025;					\
	FOR_LL( i , 0 , m_size_k ){				\
	  ll& m_ki = m_k[i];					\
	  ll (&Ei)[NM] = E[m_ki];				\
	  FOR_LL( j , 0 , m_size_h ){				\
	    ll& m_hj = m_h[j];					\
	    ll& Eij = Ei[m_hj];					\
	    if( Eij < E_min_kh ){				\
	      E_min_kh = E_min[k1][k0] = Eij;			\
	      ll (&near_hk)[2] = near[k1][k0];			\
	      near_kh[0] = near_hk[1] = m_ki;			\
	      near_kh[1] = near_hk[0] = m_hj;			\
	    }							\
	  }							\
	}							\
      }								\
      ll (&near_kk)[2] = near_k[k0];				\
      if( m_size_k == 1 ){					\
	near_kk[0] = near_kk[1] = m_k[0];			\
      } else if( m_size_k > 1 ){				\
	ll& E_min_max_kk = E_min_k[k0];				\
	E_min_max_kk = -1;					\
	FOR_LL( i , 0 , m_size_k ){				\
	  ll& m_ki = m_k[i];					\
	  ll (&Ei)[NM] = E[m_ki];				\
	  ll E_min_kk = 50000025;				\
	  ll m_ki_min;						\
	  ll m_kj_min;						\
	  FOR_LL( j , 0 , m_size_k ){				\
	    if( j != i ){					\
	      ll& m_kj = m_k[j];				\
	      ll& Eij = Ei[m_kj];				\
	      if( Eij < E_min_kk ){				\
		E_min_kk = Eij;					\
		m_ki_min = m_ki;				\
		m_kj_min = m_kj;				\
	      }							\
	    }							\
	  }							\
	  if( E_min_kk > E_min_max_kk ){			\
	    E_min_max_kk = E_min_kk;				\
	    near_kk[0] = m_ki_min;				\
	    near_kk[1] = m_kj_min;				\
	  }							\
	}							\
      }								\
    }								\
    setting = false;						\
    FOR_LL( k , 0 , P_valid ){					\
      ll& k0 = k_valid[k];					\
      ll& m_size_k = m_size[k0];				\
      if( m_size_k > 2 ){					\
	ll (&near_k)[P][2] = near[k0];				\
	FOR_LL( h , 0 , P_valid ){				\
	  if( h != k ){						\
	    ll& k1 = k_valid[h];				\
	    ll& m_size_h = m_size[k1];				\
	    if( m_size_h + 1 < m_size_k ){			\
	      ll (&near_kh)[2] = near_k[k1];			\
	      ll& near_kh0 = near_kh[0];			\
	      ll& near_kh1 = near_kh[1];			\
	      if( D[near_kh0][near_kh1] < 1000000 / P_valid ){	\
		ll& p_k0 = p[near_kh0];				\
		if( p_k0 == k0 ){				\
		  p_k0 = k1;					\
		  ll (&m_ki)[NM] = m[k0];			\
		  FOR_LL( h , 0 , m_size_k ){			\
		    if( m_ki[h] == near_kh0 ){			\
		      FOR_LL( r , h + 1 , m_size_k ){		\
			m_ki[r - 1] = m_ki[r];			\
		      }						\
		      h = m_size_k;				\
		    }						\
		  }						\
		  m[k1][m_size_h] = near_kh0;			\
		  m_size_k--;					\
		  m_size_h++;					\
		  setting = true;				\
		  if( m_size_k <= NM / P + 1 ){			\
		    h = P_valid;				\
		  }						\
		}						\
	      }							\
	    }							\
	  }							\
	}							\
      }								\
    }								\
  }								\
								\
  

template <ll NM , ll path_lim>
void GeneratePath( ll& f , ll (&path)[path_lim] , const ll& length , const ll (&m_k)[NM] , const ll& m_size_k , const ll& i_start , const ll& i_finish );

int main()
{
  constexpr const ll N = 100;
  constexpr const ll M = 8;
  constexpr const ll Px = 5;
  constexpr const ll Py = 4;
  constexpr const ll W = ( 1000 / Px ) + 1;
  constexpr const ll H = ( 1000 / Py ) + 1;
  constexpr const ll P = Px * Py;
  constexpr const ll NM = N + M;
  constexpr const ll path_lim = 100;
  constexpr const ll f_lim = 10000;
  CIN( ll , N_dummy );
  CIN( ll , M_dummy );
  ll a[NM];
  ll b[NM];
  ll p[NM];
  ll m[P][NM];
  ll m_size[P] = {};
  FOR_LL( num , 0 , N ){
    CIN( ll , a_num );
    CIN( ll , b_num );
    SetAB( a_num , b_num );
  }
  ll D[NM][NM];
  ll E[NM][NM];
  FOR_LL( i , 0 , N ){
    ll (&Di)[NM] = D[i];
    ll (&Ei)[NM] = E[i];
    FOR_LL( j , 0 , i ){
      ll dx = a[i] - a[j];
      ll dy = b[i] - b[j];
      ll Dij = dx * dx + dy * dy;
      Di[j] = D[j][i] = Dij;
      Ei[j] = E[j][i] = Dij * 25;
    }
  }
  ll E_min[P][P];
  ll near[P][P][2];
  ll P_valid;
  ll k_valid[P];
  SetNear;
  FOR_LL( num , N , NM ){
    ll E_min_min_max = 0;
    ll k_max;
    ll h_max;
    FOR_LL( k , 0 , P_valid ){
      ll& k0 = k_valid[k];
      if( m_size[k0] > 0 ){
	ll (&E_min_k)[P] = E_min[k0];
	ll E_min_min_k = 50000025;
	ll h_k;
	FOR_LL( h , 0 , P_valid ){
	  ll& k1 = k_valid[h];
	  if( m_size[k1] > 0 ){
	    ll& E_min_kh = E_min_k[k1];
	    if( E_min_min_k > E_min_kh ){
	      E_min_min_k = E_min_kh;
	      h_k = k1;
	    }
	  }
	}
	if( E_min_min_max < E_min_min_k ){
	  E_min_min_max = E_min_min_k;
	  k_max = k0;
	  h_max = h_k;
	}
      }
    }
    ll (&near_kh)[2] = near[k_max][h_max];
    ll& i_min = near_kh[0];
    ll& j_min = near_kh[1];
    ll x_min = ( a[i_min] + a[j_min] ) / 2;
    ll y_min = ( b[i_min] + b[j_min] ) / 2;
    cout << x_min << " " << y_min << endl;
    SetAB( x_min , y_min );
    ll (&D_num)[NM] = D[num];
    ll (&E_num)[NM] = E[num];
    FOR_LL( j , 0 , num ){
      ll dx = x_min - a[j];
      ll dy = y_min - b[j];
      ll D_numj = dx * dx + dy * dy;
      D_num[j] = D[j][num] = D_numj;
      E_num[j] = E[j][num] = D_numj * ( j < N ? 5 : 1 );
    }
    SetNear;
  }
  if( P_valid == 1 ){
    ll& k0 = k_valid[0];
    ll (&m_k)[NM] = m[k0];
    ll& m_size_k = m_size[k0];
    ll length_lim = min( m_size_k + 3 , m_size_k * 2 );
    ll path_00[path_lim];
    ll path_length_00;
    ll path_E_00;
    bool computed_path_E_00 = false;
    FOR_LL( length , m_size_k , length_lim ){
      FOR_LL( f , 0 , f_lim ){
	ll f_copy = f;
	ll path_current[path_lim];
	GeneratePath<NM,path_lim>( f_copy , path_current , length , m_k , m_size_k , 0 , 0 );
	if( f_copy > m_size_k ){
	  f = f_lim;
	} else {
	  ll path_E_current = 0;
	  FOR_LL( i , 1 , length ){
	    ll& m_ki = path_current[i];;
	    ll& m_kj = path_current[i - 1];
	    path_E_current += E[m_ki][m_kj];
	  }
	  if( computed_path_E_00 ? path_E_00 > path_E_current : true ){
	    path_E_00 = path_E_current;
	    FOR_LL( i , 0 , length ){
	      path_00[i] = path_current[i];
	    }
	    path_length_00 = length;
	    if( ! computed_path_E_00 ){
	      computed_path_E_00 = true;
	    }
	  }
	}
      }
    }
    ll& V = path_length_00;
    cout << V << endl;
    FOR_LL( num , 0 , V ){
      ll& i = path_00[num];
      if( i < N ){
	cout << 1 << " " << i << endl;
      } else {
	cout << 2 << " " << i - N << endl;
      }
    }
    return 0;
  }
  ll path[NM][NM][path_lim];
  ll path_length[NM][NM];
  ll path_E[NM][NM];
  bool computed_path_E[NM][NM] = {};
  FOR_LL( k , 0 , P_valid ){
    ll& k0 = k_valid[k];
    ll (&m_k)[NM] = m[k0];
    ll& m_size_k = m_size[k0];
    ll length_lim = min( m_size_k + 3 , m_size_k * 2 );
    if( m_size_k == 1 ){
      ll& m_ki = m_k[0];
      path[m_ki][m_ki][0] = m_ki;
      path_length[m_ki][m_ki] = 1;
      path_E[m_ki][m_ki] = 0;
      computed_path_E[0][0] = true;
    } else if( m_size_k > 1 ){
      FOR_LL( h0 , 0 , P_valid ){
	if( h0 != k ){
	  ll& k1 = k_valid[h0];
	  ll& i_start = near[k1][k0][1];
	  bool (&computed_path_E_i)[NM] = computed_path_E[i_start];
	  FOR_LL( h1 , 0 , P_valid ){
	    if( h1 != k && h1 != h0 ){
	      ll& k2 = k_valid[h1];
	      ll& i_finish = near[k0][k2][0];
	      bool& computed_path_E_ij = computed_path_E_i[i_finish];
	      if( ! computed_path_E_ij ){
		FOR_LL( length , m_size_k , length_lim ){
		  FOR_LL( f , 0 , f_lim ){
		    ll f_copy = f;
		    ll path_current[path_lim];
		    GeneratePath<NM,path_lim>( f_copy , path_current , length , m_k , m_size_k , i_start , i_finish );
		    if( f_copy > m_size_k ){
		      f = f_lim;
		    } else {
		      ll path_E_current = 0;
		      FOR_LL( i , 1 , length ){
			ll& m_ki = m_k[path_current[i]];
			ll& m_kj = m_k[path_current[i - 1]];
			path_E_current += E[m_ki][m_kj];
		      }
		      ll& path_E_ij = path_E[i_start][i_finish];
		      if( computed_path_E_ij ? path_E_ij > path_E_current : true ){
			path_E_ij = path_E[i_finish][i_start] = path_E_current;
			ll (&path_ij)[path_lim] = path[i_start][i_finish];
			ll (&path_ji)[path_lim] = path[i_finish][i_start];
			FOR_LL( i , 0 , length ){
			  path_ij[i] = path_current[i];
			  path_ji[i] = path_current[length - 1 - i];
			}
			path_length[i_start][i_finish] = path_length[i_finish][i_start] = length;
			if( ! computed_path_E_ij ){
			  computed_path_E_ij = computed_path_E[i_finish][i_start] = true;
			}
		      }
		    }
		  }
		}
	      }
	    }
	  }
	}
      }
    }
  }
  ll PATH[4][P] =
    {
      { 0 , 1 , 2 , 3 , 4 , 9 , 8 , 7 , 6 , 11 , 12 , 13 , 14 , 19 , 18 , 17 , 16 , 15 , 10 , 5 } ,
      { 0 , 1 , 2 , 3 , 4 , 9 , 8 , 7 , 12 , 13 , 14 , 19 , 18 , 17 , 16 , 15 , 10 , 11 , 6 , 5 } ,
      { 0 , 1 , 2 , 3 , 4 , 9 , 8 , 13 , 14 , 19 , 18 , 17 , 16 , 15 , 10 , 11 , 12 , 7 , 6 , 5 } ,
      { 0 , 1 , 2 , 3 , 4 , 9 , 14 , 19 , 18 , 17 , 16 , 15 , 10 , 11 , 12 , 13 , 8 , 7 , 6 , 5 }
    };
  ll E_sum_min = 50000025 * P * 2;
  ll s_min;
  ll k0;
  ll k1;
  ll k2;
  FOR_LL( s , 0 , 4 ){
    ll (&PATH_s)[P] = PATH[s];
    ll E_sum = 0;
    k0 = 0;
    while( m_size[PATH_s[k0]] == 0 ){
      k0++;
    }
    k1 = k0 + 1;
    while( m_size[PATH_s[k1]] == 0 ){
      k1++;
    }
    k2 = ( k1 + 1 ) % P;
    while( m_size[PATH_s[k2]] == 0 ){
      k2 = ( k2 + 1 ) % P;
    }
    FOR_LL( k , 0 , P_valid ){
      ll& PATH_s_1 = PATH_s[k1];
      E_sum += E_min[PATH_s[k0]][PATH_s_1] + path_E[near[PATH_s[k0]][PATH_s_1][1]][near[PATH_s_1][PATH_s[k2]][0]];
      k0 = k1;
      k1 = k2;
      k2 = ( k2 + 1 ) % P;
      while( m_size[PATH_s[k2]] == 0 ){
	k2 = ( k2 + 1 ) % P;
      }
    }
    if( E_sum_min > E_sum ){
      E_sum_min = E_sum;
      s_min = s;
    }
  }
  ll (&PATH_min)[P] = PATH[s_min];
  ll& p0 = p[0];
  ll k_start;
  FOR_LL( k , 0 , P ){
    if( PATH_min[k] == p0 ){
      k_start = k;
    }
  }
  ll P_valid_minus = P_valid - 1;
  k0 = ( k_start + P_valid_minus ) % P;
  while( m_size[PATH_min[k0]] == 0 ){
    k0 = ( k0 + P_valid_minus ) % P;
  }
  k1 = k_start;
  k2 = ( k1 + 1 ) % P;
  while( m_size[PATH_min[k2]] == 0 ){
    k2 = ( k2 + 1 ) % P;
  }
  ll& PATH_min_start_1 = PATH_min[k1];
  ll& near_k_start_0 = near[PATH_min[k0]][PATH_min_start_1][1];
  ll& near_k_start_1 = near[PATH_min_start_1][PATH_min[k2]][0];
  ll (&path_k_start)[path_lim] = path[near_k_start_0][near_k_start_1];
  ll& path_length_k_start = path_length[near_k_start_0][near_k_start_1];
  ll num_start;
  FOR_LL( num , 0 , path_length_k_start ){
    if( path_k_start[num] == 0 ){
      num_start = num;
      num = path_length_k_start;
    }
  }
  ll V = 1;
  FOR_LL( k , 0 , P_valid ){
    ll& PATH_min_1 = PATH_min[k1];
    V += path_length[near[PATH_min[k0]][PATH_min_1][1]][near[PATH_min_1][PATH_min[k2]][0]];
    k0 = k1;
    k1 = k2;
    k2 = ( k2 + 1 ) % P ;
    while( m_size[PATH_min[k2]] == 0 ){
      k2 = ( k2 + 1 ) % P;
    }
  }
  cout << V << endl;
  FOR_LL( num , num_start , path_length_k_start ){
    ll& i = path_k_start[num];
    if( i < N ){
      cout << 1 << " " << i + 1 << endl;
    } else {
      cout << 2 << " " << i - N + 1 << endl;
    }
  }
  k0 = k_start;
  k1 = ( k0 + 1 ) % P;
  while( m_size[PATH_min[k1]] == 0 ){
    k1 = ( k1 + 1 ) % P;
  }
  k2 = ( k1 + 1 ) % P;
  while( m_size[PATH_min[k2]] == 0 ){
    k2 = ( k2 + 1 ) % P;
  }
  REPEAT( P_valid_minus ){
    ll& PATH_min_1 = PATH_min[k1];
    ll& near_k_0 = near[PATH_min[k0]][PATH_min_1][1];
    ll& near_k_1 = near[PATH_min_1][PATH_min[k2]][0];
    ll (&path_k)[path_lim] = path[near_k_0][near_k_1];
    ll& path_length_k = path_length[near_k_0][near_k_1];
    FOR_LL( num , 0 , path_length_k ){
      ll& i = path_k[num];
      if( i < N ){
	cout << 1 << " " << i + 1 << endl;
      } else {
	cout << 2 << " " << i - N + 1 << endl;
      }
    }
    k0 = k1;
    k1 = k2;
    k2 = ( k2 + 1 ) % P;
    while( m_size[PATH_min[k2]] == 0 ){
      k2 = ( k2 + 1 ) % P;
    }
  }
  FOR_LL( num , 0 , num_start ){
    ll& i = path_k_start[num];
    if( i < N ){
      cout << 1 << " " << i + 1 << endl;
    } else {
      cout << 2 << " " << i - N + 1 << endl;
    }
  }
  cout << 1 << " " << 1 << endl;
  return 0;
}

template <ll NM , ll path_lim>
void GeneratePath( ll& f , ll (&path)[path_lim] , const ll& length , const ll (&m_k)[NM] , const ll& m_size_k , const ll& i_start , const ll& i_finish )
{

  ll d = length - m_size_k;
  ll r = 1;
  ll c;
  bool insert_num[path_lim] = {};
  FOR_LL( i , 0 , d ){
    c = length - ( r + 1 ) - ( d - i ) + 1;
    r += f % c;
    insert_num[r] = true;
    f /= c;
  }
  ll length_minus = length - 1;
  bool used[path_lim] = {};
  path[0] = i_start;
  path[length_minus] = i_finish;
  used[i_start] = used[i_finish] = true;
  c = m_size_k;
  FOR_LL( i , 1 , length_minus ){
    if( insert_num[i] ){
      path[i] = m_k[f % m_size_k];
      f /= m_size_k;
    } else {
      ll r = f % c;
      f /= c;
      r++;
      FOR_LL( j , 0 , r ){
	if( used[j] ){
	  r++;
	}
      }
      r--;
      path[i] = m_k[r];
      used[r] = true;
      c--;
    }
  }
  return;
}
0