結果

問題 No.3580 二成分の和
コンテスト
ユーザー 👑 p-adic
提出日時 2024-01-01 18:00:54
言語 C++17(gcc12)
(gcc 12.4.0 + boost 1.89.0)
コンパイル:
g++-12 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 119 ms / 2,000 ms
コード長 7,806 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,343 ms
コンパイル使用メモリ 237,648 KB
実行使用メモリ 15,360 KB
最終ジャッジ日時 2026-07-03 20:55:33
合計ジャッジ時間 4,910 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:234:28: warning: narrowing conversion of ‘(N * B)’ from ‘std::decay_t<const int>’ {aka ‘int’} to ‘uint’ {aka ‘unsigned int’} [-Wnarrowing]
  234 |   UnionFindForest<> uff{ N * B };
      |                          ~~^~~

ソースコード

diff #
raw source code 

#ifdef DEBUG
  #define _GLIBCXX_DEBUG
  #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ); signal( SIGABRT , &AlertAbort )
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , DEBUG_VALUE )
  #define CERR( MESSAGE ) cerr << MESSAGE << endl;
  #define COUT( ANSWER ) cout << ANSWER << endl
  #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック： " << ( MIN ) << ( ( MIN ) <= A ? "<=" : ">" ) << A << ( A <= ( MAX ) ? "<=" : ">" ) << ( MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) )
#else
  #pragma GCC optimize ( "O3" )
  #pragma GCC optimize( "unroll-loops" )
  #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
  #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr )
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE )
  #define CERR( MESSAGE ) 
  #define COUT( ANSWER ) cout << ANSWER << "\n"
  #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
#endif
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
#define MAIN main
#define TYPE_OF( VAR ) decay_t<decltype( VAR )>
#define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE
#define CIN( LL , A ) LL A; cin >> A
#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 QUIT return 0
#define SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX )
#define RETURN( ANSWER ) COUT( ( ANSWER ) ); QUIT

#ifdef DEBUG
  inline void AlertAbort( int n ) { CERR( "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); }
#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&

// Tが加法について可換群をなす場合にのみサポート。

// - 構築 O(size)

// - 一点根取得 O(α(size))
// - 全根取得 O(size)
// - 根数取得 O(1)

// - 二点符号付き重み取得 O(α(size))
// - 二点接合 O(α(size))
template <typename T = int>
class UnionFindForest
{

private:
  uint m_node_size;
  uint m_root_size;
  vector<uint> m_pred;
  vector<uint> m_height;
  // m_w[num]はnum番目のnodeがrootならば0、rootでないならば親nodeへ向かうパスの符号付き重み
  vector<T> m_w;
  
public:
  inline UnionFindForest( const uint& size );

  // num番目のnodeのrootを計算して返す。
  const uint& RootOfNode( const uint& num );
  // rootを全て格納する。
  template <template <typename...> typename V> void SetRoot( V<uint>& a ) const;

  // num1番目のnodeからnum0番目のnodeへ向かうパスの符号付き重みを返す。
  inline T Weight( const uint& num0 , const uint& num1 );
  
  inline const uint& SizeOfNode() const noexcept;
  inline const uint& SizeOfRoot() const noexcept;

  // num1番目のnodeからnum0番目のnodeへ符号付き重みwの有向辺を結ぶ操作と整合的に
  // なるようにrootを接合。符号付き重みの整合性が取れない場合はfalseを返す。
  bool Graft( const uint& num0 , const uint& num1 , const T& w = 0 );
  
};

template <typename T> inline UnionFindForest<T>::UnionFindForest( const uint& size ) : m_node_size( size ) , m_root_size( m_node_size ) , m_pred( m_node_size ) , m_height( m_node_size , 1 ) , m_w( m_node_size ) { for( uint i = 0 ; i < m_node_size ; i++ ){ m_pred[i] = i; } }

template <typename T>
const uint& UnionFindForest<T>::RootOfNode( const uint& num )
{

  uint& pred1 = m_pred[num];

  while( true ){
    
    uint& pred2 = m_pred[pred1];

    if( pred1 == pred2 ){

      break;

    }

    m_w[num] += m_w[pred1] += m_w[pred2];
    pred1 = pred2 = m_pred[pred2];

  }

  return pred1;

}

template <typename T> template <template <typename...> typename V>
void UnionFindForest<T>::SetRoot( V<uint>& a ) const
{

  a.clear();

  for( uint i = 0 ; i < m_node_size ; i++ ){

    if( i == m_pred[i] ){
      
      a.push_back( i );

    }

  }

  return;

}

template <typename T>
T UnionFindForest<T>::Weight( const uint& num0 , const uint& num1 )
{

  assert( num0 < m_node_size && num1 < m_node_size );
  const uint& root0 = RootOfNode( num0 );
  const uint& root1 = RootOfNode( num1 );
  assert( root0 == root1 );
  return m_w[num1] - m_w[num0];

}

template <typename T> inline const uint& UnionFindForest<T>::SizeOfNode() const noexcept { return m_node_size; }
template <typename T> inline const uint& UnionFindForest<T>::SizeOfRoot() const noexcept { return m_root_size; }

template <typename T>
bool UnionFindForest<T>::Graft( const uint& num0 , const uint& num1 , const T& w )
{

  assert( num0 < m_node_size && num1 < m_node_size );
  const uint& root0 = RootOfNode( num0 );
  const uint& root1 = RootOfNode( num1 );

  if( root0 == root1 ){

    return Weight( num0 , num1 ) == w;
    
  }

  uint& height0 = m_height[root0];
  const uint& height1 = m_height[root1];
  const uint* p_removed_root;
  const uint* p_removed_node;
  const uint* p_kept_root;

  if( height0 < height1 ){

    p_removed_root = &root0;
    p_removed_node = &num0;
    p_kept_root = &root1;
    m_w[*p_removed_root] -= w - m_w[num1] + m_w[num0];

  } else {

    if( height0 == height1 ){

      height0++;

    }

    p_removed_root = &root1;
    p_removed_node = &num1;
    p_kept_root = &root0;
    m_w[*p_removed_root] += w - m_w[num1] + m_w[num0];

  }

  if( *p_removed_node != *p_removed_root ){

    m_w[*p_removed_node] += m_w[*p_removed_root];

  }
  
  m_pred[*p_removed_node] = m_pred[*p_removed_root] = *p_kept_root;
  m_root_size--;
  return true;

}

inline DEXPR( int , bound_N , 1000 , 5 ); // 0が3個
TYPE_OF( bound_N ) N;
inline DEXPR( int , bound_M , 1000 , 5 ); // 0が3個
TYPE_OF( bound_M ) M;

int MAIN()
{
  UNTIE;

  SET_ASSERT( N , 1 , bound_N );
  SET_ASSERT( M , 1 , bound_M );
  CEXPR( int , bound_B , 1000 );
  CIN_ASSERT( B , 1 , bound_B );
  int B_minus = B - 1;

  UnionFindForest<> uff{ N * B };
  FOR( m , 0 , M ){
    CIN_ASSERT( i , 1 , N );
    CIN_ASSERT( j , 1 , N );
    CIN_ASSERT( c , 0 , B_minus );
    i--;
    j--;
    FOR( x , 0 , B ){
      uff.Graft( i + x * N , j + ( c < x ? c + B - x : c - x ) * N );
    }
  }

  vector<bool> connected_component_NG( N * B );
  FOR( i , 0 , N ){
    set<int> temp{};
    FOR( x , 0 , B ){
      const int& connected_component_num_ix = uff.RootOfNode( i + x * N );
      if( temp.count( connected_component_num_ix ) == 1 ){
	connected_component_NG[connected_component_num_ix] = true;
      } else {
	temp.insert( connected_component_num_ix );
      }
    }
  }
  
  vector<bool> connected_component_OK( N * B );
  int X[bound_N];
  FOR( i , 0 , N ){
    int& Xi = X[i] = -1;
    FOR( x , 0 , B ){
      const int& connected_component_num_ix = uff.RootOfNode( i + x * N );
      if( connected_component_OK[connected_component_num_ix] ){
	Xi = x;
	break;
      }
    }
    if( Xi == -1 ){
      FOR( x , 0 , B ){
	const int& connected_component_num_ix = uff.RootOfNode( i + x * N );
	if( !connected_component_NG[connected_component_num_ix] ){
	  connected_component_OK[connected_component_num_ix] = true;
	  Xi = x;
	  break;
	}
      }
    }
    if( Xi == -1 ){
      RETURN( "No" );
    }
  }

  COUT( "Yes" );
  int N_minus = N - 1;
  FOR( i , 0 , N ){
    cout << X[i] << " \n"[i==N_minus];
  }
  QUIT;
}
0