Submission #328432

#	Time	Username	Problem	Language	Result	Execution time	Memory
328432		kshitij_sodani	Sjekira (COCI20_sjekira)	C++14	110 / 110	78 ms	10464 KiB

sjekira

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
llo n;
llo it[100001];
vector<pair<llo,llo>> ss; 
llo par[100001];
vector<llo> adj[100001];
llo find(llo no){
	if(par[no]==no){
		return no;
	}
	par[no]=find(par[no]);
	return par[no];
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(llo i=0;i<n;i++){
		cin>>it[i];
		ss.pb({it[i],i});
		par[i]=i;
	}
	sort(ss.begin(),ss.end());
	for(llo i=0;i<n-1;i++){
		llo aa,bb;
		cin>>aa>>bb;
		aa--;
		bb--;
		adj[aa].pb(bb);
		adj[bb].pb(aa);
	}
	llo ans=0;

	for(auto j:ss){
		for(auto i:adj[j.b]){
			if(it[i]<it[j.b] or (it[i]==it[j.b] and i<j.b)){
				llo ii=find(i);
				ans+=j.a+it[ii];
				par[ii]=j.b;
			}
		}
	}



	cout<<ans<<endl;


 
 
	return 0;
}

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