제출 #947152

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
947152		NK_	Sjekira (COCI20_sjekira)	C++17	110 / 110	34 ms	4820 KiB

sjekira

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back

template<class T> using V = vector<T>;
template<class T, size_t SZ> using AR = array<T, SZ>;

using ll = long long;

const int nax = 1e5+5;
int e[nax], mx[nax];

int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
void unite(int x, int y) {
	x = get(x), y = get(y);

	if (e[x] > e[y]) swap(x, y);
	e[x] += e[y]; e[y] = x; mx[x] = max(mx[x], mx[y]);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;

	for(int i = 0; i < N; i++) {
		cin >> mx[i];
		e[i] = -1;
	}

	V<AR<int, 3>> E; for(int i = 0; i < N - 1; i++) {
		int u, v; cin >> u >> v; --u, --v;
		E.pb({max(mx[u], mx[v]), u, v});
	}

	sort(begin(E), end(E));

	ll ans = 0;
	for(auto& [w, u, v] : E) {
		ans += mx[get(u)] + mx[get(v)];
		unite(u, v);
	}

	cout << ans << nl;

	exit(0-0);
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60