Submission #445485

#	Time	Username	Problem	Language	Result	Execution time	Memory
445485		grt	Sjekira (COCI20_sjekira)	C++17	40 / 110	61 ms	7716 KiB

sjekira

#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 100 * 1000 + 10;
int n;
pi val[nax];
int par[nax], siz[nax], mx[nax];
vi V[nax];

int Fund(int x) {
	if(par[x] != x) par[x] = Fund(par[x]);
	return par[x];
}

void Onion(int a, int b) {
	a = Fund(a); b = Fund(b);
	if(a == b) return;
	if(siz[a] < siz[b]) swap(a, b);
	siz[a] += siz[b];
	mx[a] = max(mx[a], mx[b]);
	par[b] = a;
}

ll ans;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		par[i] = i;
		siz[i] = 1;
		cin >> mx[i];
		val[i] = {mx[i], i};
	}
	for(int a,b,i = 1; i < n; ++i) {
		cin >> a >> b;
		V[a].PB(b);
		V[b].PB(a);
	}
	sort(val + 1, val + n + 1);
	for(int i = 1; i <= n; ++i) {
		int u = val[i].ND;
		for(auto nbh : V[u]) {
			if(mx[Fund(nbh)] < val[i].ST) {
				if(Fund(nbh) != Fund(u)) {
					ans += val[i].ST;
					ans += mx[Fund(nbh)];
					Onion(nbh, u);
				}
			}
		}
	}
	cout << ans;
}

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