Submission #328518

#	Time	Username	Problem	Language	Result	Execution time	Memory
328518		chubyxdxd	Sjekira (COCI20_sjekira)	C++11	110 / 110	124 ms	4700 KiB

sjekira

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
int p[100010];
int mx[100010];
int val[100010];
vector<ii> v;
bool comp(ii a,ii b){
  ll x=max(val[a.first],val[a.second]);
  ll y=max(val[b.first],val[b.second]);
  return x<y;
}
int findset(int x){
  if(x==p[x])return x;
  return p[x]=findset(p[x]);
}
ll ans=0;
void unionset(int i,int j){
  i=findset(i);
  j=findset(j);
  if(i!=j){
    ans+=mx[i]+mx[j];
    mx[j]=max(mx[i],mx[j]);
    p[i]=j;
  }
}
int main(){
  int n;
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>val[i];
    mx[i]=val[i];
    p[i]=i;
  }
  int a,b;
  for(int i=1;i<n;i++){
    cin>>a>>b;
    v.push_back(ii(a,b));
  }
  sort(v.begin(),v.end(),comp);
  for(int i=0;i<n-1;i++){
    unionset(v[i].first,v[i].second);
  }
  cout<<ans<<endl;
}

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