Submission #1110884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110884		vako_p	Sjekira (COCI20_sjekira)	C++14	110 / 110	42 ms	11888 KiB

sjekira

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int mxN = 1e5 + 5;
ll n,ans;
pair<ll,ll> val[mxN];
vector<ll> v[mxN];

struct ds{
	vector<ll> par,rank,mx;
	
	void init(){
		par.resize(n + 1);
		rank.assign(n + 1, 0LL);
		mx.resize(n + 1);
		for(int i = 0; i <= n; i++){
			par[i] = i;
			mx[i] = val[i].first;
		}
	}
	
	ll find(ll at){
		if(par[at] == at) return at;
		return par[at] = find(par[at]);
	}
	
	void merge(ll p1, ll p2){
		p1 = find(p1); p2 = find(p2);
		if(p1 == p2) return;
		if(rank[p1] < rank[p2]) swap(p1, p2);
		ans += mx[p1] + mx[p2];
		par[p2] = p1;
		rank[p1] += (rank[p1] == rank[p2]);
		mx[p1] = max(mx[p1], mx[p2]);
	}
};

int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> val[i].first;
		val[i].second = i;
	}
	ds s;
	s.init();
	for(int i = 0; i < n - 1; i++){
		ll a,b;
		cin >> a >> b;
		if(val[a].first < val[b].first) swap(a, b);
		v[a].pb(b);
	}
	sort(val + 1, val + n + 1);
	for(int i = 1; i <= n; i++){
		ll at = val[i].second;
		for(auto it : v[at]){
			s.merge(at, it);	
		}
	}
 	cout << ans;
}

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