Submission #1153913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153913		siewjh	Sjekira (COCI20_sjekira)	C++20	110 / 110	36 ms	9032 KiB

sjekira

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
int p[MAXN], rnk[MAXN];
ll larg[MAXN], ans;
vector<int> adj[MAXN];
int root(int x){
	if (p[x] == -1) return x;
	return p[x] = root(p[x]);
}
void join(int ra, int rb){
	if (rnk[ra] > rnk[rb]) swap(ra, rb);
	p[ra] = rb;
	if (rnk[ra] == rnk[rb]) rnk[rb]++;
	ans += larg[ra] + larg[rb];
	larg[rb] = max(larg[rb], larg[ra]);
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int nodes; cin >> nodes;
	vector<pair<ll, int>> vec(nodes + 1);
	for (int i = 1; i <= nodes; i++){
		ll v; cin >> v;
		vec[i] = {v, i};
	}
	sort(vec.begin(), vec.end());
	for (int i = 1; i < nodes; i++){
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	vector<bool> in(nodes + 1, 0);
	memset(p, -1, sizeof(p));
	for (auto &[v, i] : vec){
		larg[i] = v;
		for (int nn : adj[i])
			if (in[nn]){
				int ra = root(i), rb = root(nn);
				join(ra, rb);
			}
		in[i] = 1;
	}
	cout << ans;
}

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