oj.uz

Submission #883680

# Submission time Handle Problem Language Result Execution time Memory
883680 2023-12-05T17:12:50 Z vjudge1 Kronican (COCI16_kronican) C++17
10 / 100
 1422 ms 464 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Incorrect 17 ms 348 KB Output isn't correct
6 Incorrect 13 ms 464 KB Output isn't correct
7 Incorrect 87 ms 436 KB Output isn't correct
8 Incorrect 155 ms 344 KB Output isn't correct
9 Incorrect 22 ms 344 KB Output isn't correct
10 Incorrect 1422 ms 456 KB Output isn't correct