Language: C++


#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <numeric>
#include <functional>
#include <tuple>

template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
  if (lhs > rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}

template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
  if (lhs < rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}

// [l, r) from l to r
struct range {
  struct itr {
    int i;
    constexpr itr(int i_): i(i_) { }
    constexpr void operator ++ () { ++i; }
    constexpr int operator * () const { return i; }
    constexpr bool operator != (itr x) const { return i != x.i; }
  };
  const itr l, r;
  constexpr range(int l_, int r_): l(std::min<int>(l_, r_)), r(r_) {}
  constexpr itr begin() const { return l; }
  constexpr itr end() const { return r; }
};

// [l, r) from r to l
struct revrange {
  struct itr {
    int i;
    constexpr itr(int i_): i(i_) { }
    constexpr void operator ++ () { --i; }
    constexpr int operator * () const { return i; }
    constexpr bool operator != (itr x) const { return i != x.i; }
  };
  const itr r, l;
  constexpr revrange(int l_, int r_): r(std::max<int>(l_, r_) - 1), l(l_ - 1) {}
  constexpr itr begin() const { return r; }
  constexpr itr end() const { return l; }
};

template <class T>
inline T scan() {
  T res;
  std::cin >> res;
  return res;
}

#define int long long

using lint = long long;
using edge = std::tuple<int, int, int, int>;
int N, M, now;
int X[100000];
edge E[100000];
std::vector<edge> graph[100000];
bool done[100000];

template <class T>
class partially_persistent_union_find {
public:
  using value_type = T;

private:
  int size;
  value_type last_query;
  const value_type inf;
  std::vector<int> parent;
  std::vector<value_type> updated;
  std::vector<std::vector<std::pair<value_type, lint>>> history;

public:
  partially_persistent_union_find(): inf(std::numeric_limits<value_type>::max()) { }
  partially_persistent_union_find(int size_): 
    inf(std::numeric_limits<value_type>::max())
  { init(size_);}

  void init(int size_) {
    size = size_;
    last_query = std::numeric_limits<value_type>::min();
    parent.assign(size_, 1);
    updated.assign(size_, inf);
    history.assign(size_, { { last_query, 0 } });
    for (int i = 0; i < size_; ++i) {
      history[i].back().second = X[i];
    }
  }

  int find_parent(int i, const value_type &t) const {
    if (updated[i] > t) {
      return i;
    }
    else {
      return find_parent(parent[i], t);
    }
  }

  int component_weight(int i, const value_type &t) const {
    i = find_parent(i, t);
    return (--std::upper_bound(history[i].begin(), history[i].end(), std::make_pair(t, std::numeric_limits<lint>::max()))) -> second;
  }

  bool unite(int i, int j, const value_type &t) {
    i = find_parent(i, last_query);
    j = find_parent(j, last_query);
    last_query = t;
    if (i == j) {
      return false;
    }
    if (parent[i] < parent[j]) {
      std::swap(i, j);
    }
    parent[i] += parent[j];
    parent[j] = i;
    updated[j] = last_query;
    lint tmp = history[i].back().second + history[j].back().second;
    history[i].emplace_back(last_query, tmp);
    return true;
  }

};

void dfs(int v) {
  if (done[v]) {
    return;
  }
  done[v] = true;
  for (auto e: graph[v]) {
    if (std::get<3>(e) > now) {
      continue;
    }
    dfs(std::get<2>(e));
  }
}

int main() {
  std::cin >> N >> M;
  for (int i: range(0, N)) {
    std::cin >> X[i];
  }
  for (int i: range(0, M)) {
    int a, b, y;
    std::cin >> a >> b >> y;
    --a; --b;
    E[i] = edge(y, a, b, 0);
  }
  std::sort(E, E + M);
  partially_persistent_union_find<int> uni(N);
  for (int i: range(0, M)) {
    int y, a, b;
    std::tie(y, a, b, std::ignore) = E[i];
    uni.unite(a, b, i);
    graph[a].emplace_back(y, a, b, i);
    graph[b].emplace_back(y, b, a, i);
  }
  int ans = 0;
  for (int i: revrange(0, M)) {
    int y, a, b;
    std::tie(y, a, b, std::ignore) = E[i];
    now = i;
    if (done[a] && done[b]) {
      continue;
    }
    if (y <= uni.component_weight(a, i)) {
      dfs(a);
    }
    else {
      ++ans;
    }
  }
  std::cout << ans << '\n';
  return 0;
}


Compiler output:
a.cc: In constructor 'partially_persistent_union_find<T>::partially_persistent_union_find()':
a.cc:89:47: error: 'numeric_limits' is not a member of 'std'
   89 |   partially_persistent_union_find(): inf(std::numeric_limits<value_type>::max()) { }
      |                                               ^~~~~~~~~~~~~~
a.cc:89:72: error: expected primary-expression before '>' token
   89 |   partially_persistent_union_find(): inf(std::numeric_limits<value_type>::max()) { }
      |                                                                        ^
a.cc:89:75: error: '::max' has not been declared; did you mean 'std::max'?
   89 |   partially_persistent_union_find(): inf(std::numeric_limits<value_type>::max()) { }
      |                                                                           ^~~
      |                                                                           std::max
In file included from /usr/include/c++/14/algorithm:61,
                 from a.cc:3:
/usr/include/c++/14/bits/stl_algo.h:5716:5: note: 'std::max' declared here
 5716 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
a.cc: In constructor 'partially_persistent_union_find<T>::partially_persistent_union_find(long long int)':
a.cc:91:14: error: 'numeric_limits' is not a member of 'std'
   91 |     inf(std::numeric_limits<value_type>::max())
      |              ^~~~~~~~~~~~~~
a.cc:91:39: error: expected primary-expression before '>' token
   91 |     inf(std::numeric_limits<value_type>::max())
      |                                       ^
a.cc:91:42: error: '::max' has not been declared; did you mean 'std::max'?
   91 |     inf(std::numeric_limits<value_type>::max())
      |                                          ^~~
      |                                          std::max
/usr/include/c++/14/bits/stl_algo.h:5716:5: note: 'std::max' declared here
 5716 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
a.cc: In member function 'void partially_persistent_union_find<T>::init(long long int)':
a.cc:96:23: error: 'numeric_limits' is not a member of 'std'
   96 |     last_query = std::numeric_limits<value_type>::min();
      |                       ^~~~~~~~~~~~~~
a.cc:96:48: error: expected primary-expression before '>' token
   96 |     last_query = std::numeric_limits<value_type>::min();
      |                                                ^
a.cc:96:51: error: '::min' has not been declared; did you mean 'std::min'?
   96 |     last_query = std::numeric_limits<value_type>::min();
      |                                                   ^~~
      |                                                   std::min
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: 'std::min' declared here
 5696 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
a.cc: In member function 'long long int partially_persistent_union_find<T>::component_weight(long long int, const value_type&) const':
a.cc:116:93: error: 'numeric_limits' is not a member of 'std'
  116 |     return (--std::upper_bound(history[i].begin(), history[i].end(), std::make_pair(t, std::numeric_limits<lint>::max()))) -> second;
      |                                                                                             ^~~~~~~~~~~~~~
a.cc:116:112: error: expected primary-expression before '>' token
  116 |     return (--std::upper_bound(history[i].begin(), history[i].end(), std::make_pair(t, std::numeric_limits<lint>::max()))) -> second;
      |                                                                                                                ^
a.cc:116:115: error: '::max' has not been declared; did you mean 'std::max'?
  116 |     return (--std::upper_bound(history[i].begin(), history[i].end(), std::make_pair(t, std::numeric_limits<lint>::max()))) -> second;
      |                                                                                                                   ^~~
      |                                                                                                                   std::max
/usr/include/c++/14/bits/stl_algo.h:5716:5: note: 'std::max' declared here
 5716 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
At global scope:
cc1plus: error: '::main' must return 'int'