Submission #872127

#	Time	Username	Problem	Language	Result	Execution time	Memory
872127		NotLinux	Sjekira (COCI20_sjekira)	C++17	110 / 110	140 ms	23752 KiB

sjekira

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int n,val[N],par[N],sz[N],mx[N];
vector < int > tree[N];
vector < pair < int , int > > order;
map < pair < int , int > , bool > vis;
int find(int a){
	if(par[a] == a)return a;
	return par[a] = find(par[a]);
}
void merge(int a , int b){
	a = find(a) , b = find(b);
	if(a == b)return;
	if(sz[a] > sz[b])swap(a,b);
	sz[b] += sz[a];
	mx[b] = max(mx[b] , mx[a]);
	par[a] = b;
}
void solve(){
	iota(par , par + N , 0);
	fill(sz , sz + N , 1);
	cin >> n;
	vector < pair < int , int > > sorted_val(n+1);
	for(int i = 1;i<=n;i++){
		cin >> val[i];
		mx[i] = val[i];
		sorted_val[i] = {val[i],i};
	}
	sort(sorted_val.begin() , sorted_val.end());
	reverse(sorted_val.begin() , sorted_val.end());
	for(int i = 1;i<n;i++){
		int u,v;cin >> u >> v;
		tree[u].push_back(v);
		tree[v].push_back(u);
	}
	for(auto itr : sorted_val){
		for(auto itr1 : tree[itr.second]){
			if(vis[{itr.second,itr1}] == 0){
				vis[{itr.second,itr1}] = vis[{itr1,itr.second}] = 1;
				order.push_back({itr1,itr.second});
			}
		}
	}
	reverse(order.begin() , order.end());
	long long ans = 0;
	for(auto itr : order){
		ans += mx[find(itr.first)] + mx[find(itr.second)];
		merge(itr.first , itr.second);
	}
	cout << ans << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

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