結果
| 問題 | No.5007 Steiner Space Travel |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2022-08-23 12:11:59 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 754 ms / 1,000 ms |
| コード長 | 14,996 bytes |
| コンパイル時間 | 2,225 ms |
| 実行使用メモリ | 4,792 KB |
| スコア | 4,686,342 |
| 最終ジャッジ日時 | 2022-08-23 12:12:19 |
| 合計ジャッジ時間 | 19,388 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge12 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 544 ms
4,440 KB |
| testcase_01 | AC | 562 ms
4,508 KB |
| testcase_02 | AC | 474 ms
4,300 KB |
| testcase_03 | AC | 516 ms
4,352 KB |
| testcase_04 | AC | 560 ms
4,792 KB |
| testcase_05 | AC | 380 ms
4,328 KB |
| testcase_06 | AC | 479 ms
4,300 KB |
| testcase_07 | AC | 478 ms
4,448 KB |
| testcase_08 | AC | 754 ms
4,692 KB |
| testcase_09 | AC | 456 ms
4,568 KB |
| testcase_10 | AC | 499 ms
4,360 KB |
| testcase_11 | AC | 398 ms
4,460 KB |
| testcase_12 | AC | 337 ms
4,328 KB |
| testcase_13 | AC | 522 ms
4,524 KB |
| testcase_14 | AC | 538 ms
4,448 KB |
| testcase_15 | AC | 596 ms
4,472 KB |
| testcase_16 | AC | 396 ms
4,364 KB |
| testcase_17 | AC | 669 ms
4,528 KB |
| testcase_18 | AC | 355 ms
4,272 KB |
| testcase_19 | AC | 518 ms
4,516 KB |
| testcase_20 | AC | 632 ms
4,552 KB |
| testcase_21 | AC | 416 ms
4,396 KB |
| testcase_22 | AC | 453 ms
4,604 KB |
| testcase_23 | AC | 331 ms
4,448 KB |
| testcase_24 | AC | 495 ms
4,504 KB |
| testcase_25 | AC | 333 ms
4,332 KB |
| testcase_26 | AC | 551 ms
4,592 KB |
| testcase_27 | AC | 474 ms
4,232 KB |
| testcase_28 | AC | 396 ms
4,152 KB |
| testcase_29 | AC | 520 ms
4,360 KB |
コンパイルメッセージ
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:426:6: 備考: ‘num_start’ はここで定義されています
426 | ll num_start;
| ^~~~~~~~~
main.cpp:422:43: 警告: ‘k_start’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
422 | ll& near_k_start_0 = near[PATH_min[k0]][PATH_min_start_1][1];
| ^~~~~~~~~~~~~~~~
main.cpp:479:30: 警告: ‘s_min’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
479 | 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:249:8: 備考: ‘path_length_00’ はここで定義されています
249 | ll path_length_00;
| ^~~~~~~~~~~~~~
main.cpp:266:11: 警告: ‘path_E_00’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
266 | 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: 備
ソースコード
#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] < 20000 / 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;
// constexpr const ll f_lim = 100000;
// constexpr const ll f_lim = 1000000;
// constexpr const ll f_lim = 1000000000;
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 length_lim = min( m_size_k + 5 , m_size_k * 2 );
ll length_lim = min( m_size_k + 7 , 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];
ll length_min = m_size_k + ( i_start == i_finish ? 1 : 0 );
if( ! computed_path_E_ij ){
FOR_LL( length , length_min , 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];
}
if( i_start != i_finish ){
FOR_LL( i , 0 , length ){
path_ji[length - 1 - i] = path_current[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 - ( i_start == i_finish ? 1 : 0 );
ll r = 0;
ll c;
bool insert_num[path_lim] = {};
FOR_LL( i , 0 , d ){
c = length - ( r + 1 ) - ( d - i );
r += ( f % c ) + 1;
f /= c;
insert_num[r] = true;
}
ll length_minus = length - 1;
bool used[path_lim] = {};
path[0] = i_start;
path[length_minus] = i_finish;
FOR_LL( i , 0 , m_size_k ){
const ll& m_ki = m_k[i];
if( m_ki == i_start || m_ki == i_finish ){
used[i] = true;
}
}
c = m_size_k - ( i_start == i_finish ? 1 : 2 );
FOR_LL( i , 1 , length_minus ){
if( insert_num[i] ){
path[i] = m_k[f % m_size_k];
f /= m_size_k;
} else {
r = ( f % c ) + 1;
f /= c;
ll num = -1;
FOR_LL( j , 0 , r ){
num++;
while( used[num] ){
num++;
}
}
path[i] = m_k[num];
used[num] = true;
c--;
}
}
return;
}