Submission #334650

#	Time	Username	Problem	Language	Result	Execution time	Memory
334650		GioChkhaidze	Sjekira (COCI20_sjekira)	C++14	110 / 110	115 ms	2932 KiB

sjekira

#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define F first
#define S second

using namespace std;

const int N=1e5+5;

ll ans;
int n,a[N],p[N],x,y;

vector < pair < int , pair < int , int > > > s;
 
int P(int x) {
	if (x==p[x]) return x;
	return p[x]=P(p[x]);
} 
 
main () {
	cin>>n;
	for (int i=1; i<=n; i++) {
		cin>>a[i];
		p[i]=i;
	}
	
	for (int i=1; i<n; i++) {
		cin>>x>>y;
		s.pb({max(a[x],a[y]),{x,y}});
	}
	
	sort(s.begin(),s.end());
	for (int i=0; i<s.size(); i++) {
		x=s[i].S.F,y=s[i].S.S;
		x=P(x),y=P(y); 
		ans+=a[x]+a[y];
		p[y]=x;
		a[x]=max(a[x],a[y]);
	}
	
	cout<<ans<<"\n";
}

Compilation message (stderr)

sjekira.cpp:22:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   22 | main () {
      |       ^
sjekira.cpp: In function 'int main()':
sjekira.cpp:35:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for (int i=0; i<s.size(); i++) {
      |                ~^~~~~~~~~

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