oj.uz

답안 #332204

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
332204 2020-12-01T16:28:33 Z DanerZein Sjekira (COCI20_sjekira) C++14
10 / 110
 136 ms 18020 KB 
#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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 136 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 56 ms 18020 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 136 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Runtime error 2 ms 748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 136 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Runtime error 56 ms 18020 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -