Language: C++

#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 100000


struct Info{
	Info(int arg_id,int arg_value){
		id = arg_id;
		value = arg_value;
	}
	bool operator<(const struct Info &arg) const{
		return value < arg.value;
	}
	int id,value;
};

struct Data{
	Data(int arg_node_id,int arg_value){
		node_id = arg_node_id;
		value = arg_value;
	}
	bool operator<(const struct Data &arg){
		return value > arg.value;
	}

	int node_id,value;
};

int N;
int contribution[NUM];
int boss[NUM],height[NUM],member_num[NUM];
int salary[NUM],in_num[NUM];
vector<Info> V[NUM];
vector<int> G[NUM];

int group_index;

int get_boss(int id){
	if(boss[id] == id)return id;
	else{
		return boss[id] = get_boss(boss[id]);
	}
}

int is_same(int x,int y){
	return get_boss(x) == get_boss(y);
}

void unite(int x,int y){
	int boss_x = get_boss(x);
	int boss_y = get_boss(y);

	if(boss_x == boss_y)return;

	if(height[x] > height[y]){

		boss[boss_y] = boss_x;

	}else if(height[x] < height[y]){

		boss[boss_x] = boss_y;

	}else{ //height[x] == height[y]

		boss[boss_y] = boss_x;
		height[x]++;
	}
}

int main(){

	scanf("%d",&N);
	for(int i = 0; i < N; i++)scanf("%d",&contribution[i]);

	for(int i = 0; i < N; i++){
		boss[i] = i;
		height[i] = 0;
		member_num[i] = 1;
	}

	int M;
	scanf("%d",&M);

	int a,b;
	for(int loop = 0; loop < M; loop++){
		scanf("%d %d",&a,&b);
		a--;
		b--;
		V[a].push_back(Info(b,contribution[b]));
		V[b].push_back(Info(a,contribution[a]));

		if(contribution[a] < contribution[b]){
			G[a].push_back(b);
		}else if(contribution[a] > contribution[b]){
			G[b].push_back(a);
		}else{ //contribution[a] == contribution[b]
			unite(a,b);
		}
	}

	for(int i = 0; i < N; i++){

		if(V[i].size() <= 1)continue;

		sort(V[i].begin(),V[i].end());
		for(int k = 1; k < V[i].size(); k++){
			if(V[i][k].value == V[i][k-1].value){
				unite(V[i][k].id,V[i][k-1].id);
			}else{ //V[i][k].value > V[i][k-1].value
				G[V[i][k-1].id].push_back(V[i][k].id);
			}
		}
	}

	int boss_id,to_boss_id;
	for(int i = 0; i < N; i++){
		boss_id = get_boss(i);
		if(boss_id == i){

			for(int k = 0; k < G[boss_id].size(); k++){
				to_boss_id = get_boss(G[boss_id][k]);
				G[boss_id][k] = to_boss_id;
			}

		}else{
			member_num[boss_id]++;

			for(int k = 0; k < G[i].size(); k++){
				G[boss_id].push_back(to_boss_id = get_boss(G[i][k]));
			}
		}
	}

	for(int i = 0; i < NUM; i++)in_num[i] = 0;

	for(int i = 0; i < N; i++){
		if(boss[i] != i)continue;

		sort(G[i].begin(),G[i].end());
		G[i].erase(unique(G[i].begin(),G[i].end()),G[i].end());

		for(int k = 0; k < G[i].size(); k++){
			in_num[G[i][k]]++;
		}
	}

	for(int i = 0; i < NUM; i++){
		salary[i] = 1;
	}

	priority_queue<Data> Q;

	for(int i = 0; i < NUM; i++){
		if(boss[i] != i)continue;

		Q.push(Data(i,contribution[i]));
	}

	while(!Q.empty()){

		for(int i = 0; i < G[Q.top().node_id].size(); i++){
			salary[G[Q.top().node_id][i]] = max(salary[G[Q.top().node_id][i]],salary[Q.top().node_id]+1);
		}
		Q.pop();
	}

	ll ans = 0;

	for(int i = 0; i < NUM; i++){
		if(boss[i] == i){
			ans += salary[i]*member_num[i];
		}
	}

	printf("%lld\n",ans);

	return 0;
}




Compiler output:
In file included from /usr/include/c++/14/bits/refwrap.h:39,
                 from /usr/include/c++/14/deque:67,
                 from /usr/include/c++/14/stack:62,
                 from a.cc:5:
/usr/include/c++/14/bits/stl_function.h: In instantiation of 'constexpr bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = Data]':
/usr/include/c++/14/bits/predefined_ops.h:196:23:   required from 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<Data*, std::vector<Data, std::allocator<Data> > >; _Value = Data; _Compare = std::less<Data>]'
  196 |         { return bool(_M_comp(*__it, __val)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_heap.h:140:48:   required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Data*, vector<Data, allocator<Data> > >; _Distance = long int; _Tp = Data; _Compare = __gnu_cxx::__ops::_Iter_comp_val<less<Data> >]'
  140 |       while (__holeIndex > __topIndex && __comp(__first + __parent, __value))
      |                                          ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_heap.h:216:23:   required from 'void std::push_heap(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<Data*, vector<Data, allocator<Data> > >; _Compare = less<Data>]'
  216 |       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  217 |                        _DistanceType(0), _GLIBCXX_MOVE(__value), __cmp);
      |                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_queue.h:747:16:   required from 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(value_type&&) [with _Tp = Data; _Sequence = std::vector<Data, std::allocator<Data> >; _Compare = std::less<Data>; value_type = Data]'
  747 |         std::push_heap(c.begin(), c.end(), comp);
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:174:9:   required from here
  174 |                 Q.push(Data(i,contribution[i]));
      |                 ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_function.h:405:20: error: no match for 'operator<' (operand types are 'const Data' and 'const Data')
  405 |       { return __x < __y; }
      |                ~~~~^~~~~
a.cc:40:14: note: candidate: 'bool Data::operator<(const Data&)' (near match)
   40 |         bool operator<(const struct Data &arg){
      |              ^~~~~~~~
a.cc:40:14: note:   passing 'const Data*' as 'this' argument discards qualifiers
In file included from /usr/include/c++/14/bits/stl_algobase.h:64,
                 from /usr/include/c++/14/bits/specfun.h:43,
                 from /usr/include/c++/14/cmath:3906,
                 from a.cc:2:
/usr/include/c++/14/bits/stl_pair.h:1045:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator<(const pair<_T1, _T2>&, const pair<_T1, _T2>&)'
 1045 |     operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_pair.h:1045:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_function.h:405:20: note:   'const Data' is not derived from 'const std::pair<_T1, _T2>'
  405 |       { return __x < __y; }
      |                ~~~~^~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:67:
/usr/include/c++/14/bits/stl_iterator.h:448:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator<(const reverse_iterator<_Iterator>&, const reverse_iterator<_Iterator>&)'
  448 |     operator<(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:448:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_function.h:405:20: note:   'const Data' is not derived from 'const std::reverse_iterator<_Iterator>'
  405 |       { return __x < __y; }
      |                ~~~~^~~~~
/usr/include/c++/14/bits/stl_iterator.h:493:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const reverse_iterator<_Iterator>&, const reverse_iterator<_IteratorR>&)'
  493 |     operator<(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:493:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_function.h:405:20: note:   'const Data' is not derived from 'const std::reverse_iterator<_Iterator>'
  405 |       { return __x < __y; }
      |                ~~~~^~~~~
/usr/include/c++/14/bits/stl_iterator.h:1694:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)'
 1694 |     operator<(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1694:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_function.h:405:20: note:   'const Data' is not derived from 'const std::move_iterator<_IteratorL>'
  405 |       { return __x < __y; }
      |                ~~~~^~~~~
/usr/include/c++/14/bits/stl_iterator.h:1760:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator<(const move_iterator<_IteratorL>&, const move_iterator<_IteratorL>&)'
 1760 |     operator<(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1760:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_function.h:405:20: note:   'const Data' is not derived from 'const std::move_iterator<_IteratorL>'
  405 |       { return __x < __y; }
      |                ~~~~^~~~~
In file included from /usr/include/c++/14/deque:66:
/usr/include/c++/14/bits/stl_deque.h:2334:5: note: candidate: 'template<class _Tp, class _Alloc> bool std::operator<(const deque<_Tp, _Alloc>&, const deque<_Tp, _Alloc>&)'
 2334 |     operator<(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_deque.h:2334:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_function.h:405:20: note:   'const Data' is not derived from 'const std::deque<_Tp, _Alloc>'
  405 |       { return __x < __y; }
      |                ~~~~^~~~~