Submission #883680

#	Time	Username	Problem	Language	Result	Execution time	Memory
883680		vjudge1	Kronican (COCI16_kronican)	C++17	10 / 100	1422 ms	464 KiB

kronican

#include <bits/stdc++.h>
using namespace std;
#define sp << " " << 
#define int long long
#define vi vector<int>
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
#define pii pair<int,int>
const int N = 21;

vi dad(N);
int find(int x) {
  if (x == dad[x]) return x;
  return dad[x] = find(dad[x]);
}
void unite(int x,int y) {
  dad[find(x)] = find(y);
}


void solve() {
  int n,k;
  cin >> n >> k;
  int a[n+1][n+1];
  F(i,n) {
    F(j,n) cin >> a[i][j];
  }
  for (int i=1;i<=n;i++) {
    for (int j=1;j<=n;j++) {
      for (int m=1;m<=n;m++) {
        a[i][j] = min(a[i][j],a[i][m]+a[m][j]);
      }
    }
  }
  int lim = (1<<n);
  int ans = 2e18;
  for (int mask = 0;mask<lim;mask++) {
    if (__builtin_popcountll(mask) != k) continue;
    priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>> edg;
    F(i,n) dad[i] = i;
    for (int j=1;j<=n;j++) {
      for (int j2=1;j2<=n;j2++) { 
        edg.push({a[j][j2],{j,j2}});
        if (mask&(1<<(j2-1))) {
          if (mask&(1<<(j-1))) unite(j,j2);
        }
      }
    }
    int cc = 0;
    int ansy = 0;
    while (edg.size()) {
      auto f =  edg.top();
      edg.pop();
      if (find(f.second.first) == find(f.second.second)) continue;
      ansy+=f.first;
      unite(f.second.first,f.second.second);
      if (mask == 18) {
        //cout << "United:" << f.second.first sp f.second.second << "for " <<f.first <<endl;
      }
      cc++;
    }
    ans = min(ans,ansy);
  }
  cout << ans << endl;
}
    
                  
                             
signed main() { 
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  #ifdef Local
  freopen("in","r",stdin);
  freopen("out","w",stdout); 
  #endif
  int t = 1;
  //cin >> t;
	F(i,t) solve();
}

• Subtask 1: 10 / 100