Submission #1153896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153896		dzuizz	Sjekira (COCI20_sjekira)	C++20	0 / 110	1095 ms	4164 KiB

sjekira

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int MAXN=100005;
int pa[MAXN],val[MAXN];
int find(int x){ return x==pa[x]?x:pa[x]=find(pa[x]); }
void merge(int a,int b){
  a=find(a),b=find(b);
  if(a==b) return;
  pa[b]=a;
  val[a]=max(val[a],val[b]);
}
signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  // Subtask 1
  int n; cin>>n;
  int t[n]; for(auto&x:t) cin>>x;
  pair<int,int> e[n-1];
  for(int i=0;i<n-1;++i)
    cin>>e[i].first>>e[i].second,--e[i].first,--e[i].second;
  int a[n-1]; iota(a,a+n-1,0);
  int ans=3e18;
  do{
    iota(pa,pa+n,0);
    for(int i=0;i<n;++i) val[i]=t[i];
    int res=0;
    for(auto[u,v]:e){
      u=find(u),v=find(v);
      res+=val[u]+val[v];
      merge(u,v);
    }
    /*if(res<ans){
      for(auto&x:a)cout<<x<<" ";
      cout<<'\n';
    */
    ans=min(ans,res);
  }while(next_permutation(a,a+n-1));
  cout<<ans<<'\n';
  return 0;
}

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