제출 #332204

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
332204		DanerZein	Sjekira (COCI20_sjekira)	C++14	10 / 110	136 ms	18020 KiB

sjekira

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
vector<ll> x,per;
ll pa[20],ma[20];
const ll MAX=1e18;
void init(ll n){
  for(ll i=0;i<n;i++){
    pa[i]=i;
    ma[i]=x[i];
  }
}
ll findset(ll i){
  if(pa[i]==i)return i;
  return pa[i]=findset(pa[i]);
}
bool issameset(ll i,ll j){
  return findset(i)==findset(j);
}
void unionset(ll i,ll j){
  if(!issameset(i,j)){
    ll u=findset(i),v=findset(j);
    pa[u]=v;
    ma[v]=max(ma[u],ma[v]);
  }
}
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ll n;
  cin>>n;
  vector<ii> con;
  map<ll,ii>no;
  for(ll i=0;i<n;i++){
    ll a; cin>>a;
    x.push_back(a);
  }
  for(ll i=0;i<n-1;i++){
    ll a,b;
    cin>>a>>b;
    a--; b--;
    no[i]=ii(a,b);
    per.push_back(i);
    con.push_back(ii(a,b));
  }
  ll mi=MAX;
  do{
    init(n);
    ll s=0;
    for(ll i=0;i<n-1;i++){
      ll id=per[i];
      ll u=no[id].first,v=no[id].second;
      s+=(ma[findset(u)]+ma[findset(v)]);
      unionset(u,v);
    }
    mi=min(mi,s);
  }while(next_permutation(per.begin(),per.end()));
  cout<<mi<<endl;
}

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