結果

問題 No.2912 ０次パーシステントホモロジー
ユーザー 👑 p-adicp-adic
提出日時 2022-11-15 16:47:15
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 62 ms / 2,000 ms
コード長 2,365 bytes
コンパイル時間 2,256 ms
コンパイル使用メモリ 205,844 KB
実行使用メモリ 7,424 KB
最終ジャッジ日時 2024-10-04 20:50:05
合計ジャッジ時間 4,079 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,144 KB
testcase_01 AC 3 ms
6,272 KB
testcase_02 AC 4 ms
6,272 KB
testcase_03 AC 3 ms
6,144 KB
testcase_04 AC 3 ms
6,144 KB
testcase_05 AC 3 ms
6,272 KB
testcase_06 AC 3 ms
6,272 KB
testcase_07 AC 3 ms
6,144 KB
testcase_08 AC 3 ms
6,272 KB
testcase_09 AC 3 ms
6,272 KB
testcase_10 AC 3 ms
6,144 KB
testcase_11 AC 3 ms
6,400 KB
testcase_12 AC 3 ms
6,144 KB
testcase_13 AC 3 ms
6,144 KB
testcase_14 AC 3 ms
6,144 KB
testcase_15 AC 6 ms
6,400 KB
testcase_16 AC 24 ms
7,296 KB
testcase_17 AC 22 ms
6,400 KB
testcase_18 AC 32 ms
6,656 KB
testcase_19 AC 58 ms
7,296 KB
testcase_20 AC 62 ms
7,296 KB
testcase_21 AC 51 ms
7,424 KB
testcase_22 AC 53 ms
7,296 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

#define CIN( LL , A ) LL A; cin >> A 
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) 
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( remove_const<remove_reference<decltype( FINAL_PLUS_ONE )>::type >::type VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) 
#define QUIT return 0 
#define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; QUIT 

#define MAIN main

class Edge
{
public:
  int m_i0;
  int m_i1;
  int m_w;
  inline Edge() = default;
};

class OrdEdge
{
public:
  inline bool operator()( const Edge& e0 , const Edge& e1 ) { return e0.m_w < e1.m_w; }
};

class Query
{
public:
  int m_r;
  int m_t;
  inline Query() = default;
};

class OrdQuery
{
public:
  inline bool operator()( const Query& q0 , const Query& q1 ) { return q0.m_r < q1.m_r; }
};

class Node
{
public:
  int m_depth;
  Node* m_root;
  inline Node() : m_depth( 0 ) , m_root( this ) {}
};

int MAIN()
{
  UNTIE;
  constexpr const int bound = 100001;
  CIN( int , N_V );
  CIN( int , N_E );
  Edge E[bound] = {};
  FOR( j , 0 , N_E ){
    Edge& ej = E[j];
    cin >> ej.m_i0;
    cin >> ej.m_i1;
    cin >> ej.m_w;
  }
  CIN( int , T );
  Query Q[bound];
  FOR( t , 0 , T ){
    Query& qt = Q[t];
    cin >> qt.m_r;
    qt.m_t = t;
  }
  sort( E , E + N_E , OrdEdge() );
  sort( Q , Q + T , OrdQuery() );
  Node Pi0G[bound] = {};
  int answer[bound];
  int j = 0;
  int cc = N_V;
  int depth_dif;
  FOR( t , 0 , T ){
    Query& qt = Q[t];
    while( j < N_E ){
      Edge& ej = E[j];
      if( ej.m_w <= qt.m_r ){
	Node& Pi0Gi0 = Pi0G[ej.m_i0];
	while( Pi0Gi0.m_root != Pi0Gi0.m_root->m_root ){
	  Pi0Gi0.m_root = Pi0Gi0.m_root->m_root;
	}
	Node& Pi0Gi1 = Pi0G[ej.m_i1];
	while( Pi0Gi1.m_root != Pi0Gi1.m_root->m_root ){
	  Pi0Gi1.m_root = Pi0Gi1.m_root->m_root;
	}
	if( Pi0Gi0.m_root != Pi0Gi1.m_root ){
	  depth_dif = Pi0Gi1.m_root->m_depth - Pi0Gi0.m_root->m_depth;
	  if( depth_dif > 0 ){
	    Pi0Gi0.m_root = Pi0Gi0.m_root->m_root = Pi0Gi1.m_root;
	  } else {
	    Pi0Gi1.m_root = Pi0Gi1.m_root->m_root = Pi0Gi0.m_root;
	    if( depth_dif == 0 ){
	      Pi0Gi0.m_root->m_depth++;
	    }
	  }
	  cc--;
	}
	j++;
      } else {
	break;
      }
    }
    answer[qt.m_t] = cc;
  }
  FOR( t , 0 , T ){
    cout << answer[t] << "\n";
  }
  QUIT;
}
0