// 誤解法(O(N^2 C + C^2)BFS)チェック #ifdef DEBUG #define _GLIBCXX_DEBUG #define SIGNAL signal( SIGABRT , &AlertAbort ); #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , DEBUG_VALUE ) #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック: " , ( MIN ) , ( ( MIN ) <= A ? "<=" : ">" ) , A , ( A <= ( MAX ) ? "<=" : ">" ) , ( MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) ) #define CERR( ... ) VariadicCout( cerr , __VA_ARGS__ ) << endl #define COUT( ... ) VariadicCout( cout << "出力: " , __VA_ARGS__ ) << endl #define CERR_A( A , N ) OUTPUT_ARRAY( cerr , A , N ) << endl #define COUT_A( A , N ) cout << "出力: "; OUTPUT_ARRAY( cout , A , N ) << endl #define CERR_ITR( A ) OUTPUT_ITR( cerr , A ) << endl #define COUT_ITR( A ) cout << "出力: "; OUTPUT_ITR( cout , A ) << endl #else #pragma GCC optimize ( "O3" ) #pragma GCC optimize ( "unroll-loops" ) #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) #define SIGNAL #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE ) #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) ) #define CERR( ... ) #define COUT( ... ) VariadicCout( cout , __VA_ARGS__ ) << "\n" #define CERR_A( A , N ) #define COUT_A( A , N ) OUTPUT_ARRAY( cout , A , N ) << "\n" #define CERR_ITR( A ) #define COUT_ITR( A ) OUTPUT_ITR( cout , A ) << "\n" #endif #include using namespace std; using ll = long long; template using T2 = pair; #define REPEAT_MAIN( BOUND ) int main(){ ios_base::sync_with_stdio( false ); cin.tie( nullptr ); SIGNAL; DEXPR( int , bound_test_case_num , BOUND , min( BOUND , 100 ) ); int test_case_num = 1; if constexpr( bound_test_case_num > 1 ){ SET_ASSERT( test_case_num , 1 , bound_test_case_num ); } REPEAT( test_case_num ){ if constexpr( bound_test_case_num > 1 ){ CERR( "testcase " , VARIABLE_FOR_REPEAT_test_case_num , ":" ); } Solve(); CERR( "" ); } } #define TYPE_OF( VAR ) decay_t #define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE #define SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX ) #define CIN_ASSERT( A , MIN , MAX ) TYPE_OF( MAX ) A; SET_ASSERT( A , MIN , MAX ) #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 AUTO_ITR( ARRAY ) auto itr_ ## ARRAY = ARRAY .begin() , end_ ## ARRAY = ARRAY .end() #define FOR_ITR( ARRAY ) for( AUTO_ITR( ARRAY ) , itr = itr_ ## ARRAY ; itr_ ## ARRAY != end_ ## ARRAY ; itr_ ## ARRAY ++ , itr++ ) #define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT_ ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES ) #define OUTPUT_ARRAY( OS , A , N ) FOR( VARIABLE_FOR_OUTPUT_ARRAY , 0 , N ){ OS << A[VARIABLE_FOR_OUTPUT_ARRAY] << (VARIABLE_FOR_OUTPUT_ARRAY==N-1?"":" "); } OS #define OUTPUT_ITR( OS , A ) { auto ITERATOR_FOR_OUTPUT_ITR = A.begin() , END_FOR_OUTPUT_ITR = A.end(); bool VARIABLE_FOR_OUTPUT_ITR = ITERATOR_FOR_COUT_ITR != END_FOR_COUT_ITR; while( VARIABLE_FOR_OUTPUT_ITR ){ OS << *ITERATOR_FOR_COUT_ITR; ( VARIABLE_FOR_OUTPUT_ITR = ++ITERATOR_FOR_COUT_ITR != END_FOR_COUT_ITR ) ? OS : OS << " "; } } OS // 入出力用 template inline basic_istream& VariadicCin( basic_istream& is ) { return is; } template inline basic_istream& VariadicCin( basic_istream& is , Arg& arg , ARGS&... args ) { return VariadicCin( is >> arg , args... ); } template inline basic_istream& VariadicGetline( basic_istream& is , const char& separator ) { return is; } template inline basic_istream& VariadicGetline( basic_istream& is , const char& separator , Arg& arg , ARGS&... args ) { return VariadicGetline( getline( is , arg , separator ) , separator , args... ); } template inline basic_ostream& VariadicCout( basic_ostream& os , const Arg& arg ) { return os << arg; } template inline basic_ostream& VariadicCout( basic_ostream& os , const Arg1& arg1 , const Arg2& arg2 , const ARGS&... args ) { return VariadicCout( os << arg1 << " " , arg2 , args... ); } // グリッド問題用 int H , W , H_minus , W_minus , HW; vector > non_wall; inline T2 EnumHW( const int& v ) { return { v / W , v % W }; } inline int EnumHW_inv( const int& h , const int& w ) { return h * W + w; } // グラフ用関数 template list E( const int& i ); template vector > e; // デバッグ用 #ifdef DEBUG inline void AlertAbort( int n ) { CERR( "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); } void AutoCheck( bool& auto_checked ); #endif // 圧縮用 #define TE template #define TY typename #define US using #define ST static #define IN inline #define CL class #define PU public #define OP operator #define CE constexpr #define CO const #define NE noexcept #define RE return #define WH while #define VO void #define VE vector #define LI list #define BE begin #define EN end #define SZ size #define MO move #define TH this #define CRI CO int& #define CRUI CO uint& #define CRL CO ll& #define DC_OF_FIRST_SEARCH(BREADTH)TE CL BREADTH ## FirstSearch_Body{PU:int m_V;int m_init;LI m_next;bool m_found[V_max];int m_prev[V_max];IN BREADTH ## FirstSearch_Body(CRI V);IN BREADTH ## FirstSearch_Body(CRI V,CRI init);IN VO Reset(CRI init);IN VO Shift(CRI init);IN CRI SZ()CO;IN CRI init()CO;IN bool& found(CRI i);IN CRI prev(CRI i)CO;int Next();virtual LI e(CRI t)= 0;};TE E(CRI)> CL BREADTH ## FirstSearch:PU BREADTH ## FirstSearch_Body{PU:TE IN BREADTH ## FirstSearch(CO Args&... args);IN LI e(CRI t);};TE E(CRI)> VO BREADTH ## FirstConnectedComponent(CRI V,int(&cc_num)[V_max],int& count); #define DF_OF_FIRST_SEARCH(BREADTH,PUSH)TE IN BREADTH ## FirstSearch_Body::BREADTH ## FirstSearch_Body(CRI V):m_V(V),m_init(),m_next(),m_found(),m_prev(){assert(m_V <= V_max);for(int i = 0;i < m_V;i++){m_prev[i] = -1;}}TE IN BREADTH ## FirstSearch_Body::BREADTH ## FirstSearch_Body(CRI V,CRI init):BREADTH ## FirstSearch_Body(V){m_init = init;m_next.push_back(m_init);m_found[m_init] = true;}TE E(CRI)> TE IN BREADTH ## FirstSearch::BREADTH ## FirstSearch(CO Args&... args):BREADTH ## FirstSearch_Body(args...){}TE IN VO BREADTH ## FirstSearch_Body::Reset(CRI init){m_init = init;assert(m_init < m_V);m_next.clear();m_next.push_back(m_init);for(int i = 0;i < m_V;i++){m_found[i] = i == m_init;m_prev[i] = -1;}}TE IN VO BREADTH ## FirstSearch_Body::Shift(CRI init){m_init = init;assert(m_init < m_V);m_next.clear();if(! m_found[m_init]){m_next.push_back(m_init);m_found[m_init] = true;}}TE IN CRI BREADTH ## FirstSearch_Body::SZ()CO{RE m_V;}TE IN CRI BREADTH ## FirstSearch_Body::init()CO{RE m_init;}TE IN bool& BREADTH ## FirstSearch_Body::found(CRI i){assert(i < m_V);RE m_found[i];}TE IN CRI BREADTH ## FirstSearch_Body::prev(CRI i)CO{assert(i < m_V);RE m_prev[i];}TE int BREADTH ## FirstSearch_Body::Next(){if(m_next.empty()){RE -1;}CO int i_curr = m_next.front();m_next.pop_front();LI edge = e(i_curr);WH(! edge.empty()){CRI i = edge.front();bool& found_i = m_found[i];if(! found_i){m_next.PUSH(i);m_prev[i] = i_curr;found_i = true;}edge.pop_front();}RE i_curr;}TE E(CRI)> IN LI BREADTH ## FirstSearch::e(CRI t){RE E(t);}TE E(CRI)> VO BREADTH ## FirstConnectedComponentSearch(CRI V,int(&cc_num)[V_max],int& count){BREADTH ## FirstSearch bfs{V};count = 0;for(int i = 0;i < V;i++){cc_num[i] = -1;}for(int i = 0;i < V;i++){if(cc_num[i] == -1){bfs.Shift(i);int j = bfs.Next();WH(j != -1?cc_num[j] == -1:false){cc_num[j] = count;j = bfs.Next();}count++;}}RE;} DC_OF_FIRST_SEARCH(Breadth);DF_OF_FIRST_SEARCH(Breadth,push_back); TE E(CRI)>VO SetDepth_Body(BreadthFirstSearch& bfs,CRI V,int ( &depth )[V_max]){for(int i = 0;i < V;i++){depth[i] = -1;}int i = bfs.Next();depth[i] = 0;WH((i = bfs.Next())!= -1){depth[i] = depth[bfs.prev( i )] + 1;}RE;}TE E(CRI)>VO SetDepth(CRI V,CRI init,int ( &depth )[V_max]){BreadthFirstSearch bfs{V,init};SetDepth_Body(bfs,V,depth);RE;}TE E(CRI)>VO SetDepth(BreadthFirstSearch& bfs,CRI V,CRI init,int ( &depth )[V_max]){bfs.Reset(init);SetDepth_Body(bfs,V,depth);RE;} vector > > f{}; template list E( const int& i ) { list answer{}; // list answer = e[i]; // VVV 入力によらない処理は以下に挿入する。 auto [x,c] = EnumHW( i ); auto& e_x = e[x]; FOR_ITR( e_x ){ int y = min( x , *itr ); int z = max( x , *itr ); if( f[z][y].empty() ? false : f[z][y][c] >= 0 ){ answer.push_back( EnumHW_inv( *itr , f[z][y][c] ) ); } } // AAA 入力によらない処理は以上に挿入する。 return answer; } inline void Solve() { CEXPR( int , bound_N , 10 ); // 0が1個 CIN_ASSERT( N , 2 , bound_N ); CIN_ASSERT( M , 1 , N * ( N - 1 ) / 2 ); CEXPR( int , bound_C , 100000 ); // 0が5個 CIN_ASSERT( C , 1 , bound_C ); H = N; W = C + 1; H_minus = H - 1; HW = H * W; e.resize( N ); f.resize( N ); FOR( j , 0 , N ){ f[j].resize( j ); } FOR( m , 0 , M ){ CIN_ASSERT( i , 1 , N ); CIN_ASSERT( j , i + 1 , N ); CIN_ASSERT( r , 1 , C ); CIN_ASSERT( w , 1 , C ); --i; --j; e[i].push_back( j ); e[j].push_back( i ); f[j][i].resize( W ); FOREQ( c , 0 , C ){ f[j][i][c] = max( -1 , c - c / r - w ); } } BreadthFirstSearch> bfs{ HW }; FOREQ( c , 1 , C ){ bfs.Shift( EnumHW_inv( 0 , c ) ); while( bfs.Next() != -1 ){} bool found = false; FOREQINV( d , C , 0 ){ if( bfs.found( EnumHW_inv( H_minus , d ) ) ){ found = true; COUT( d ); break; } } if( ! found ){ COUT( -1 ); } } } REPEAT_MAIN(1);