Submission #1216086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216086		Rafael_Augusto	Kronican (COCI16_kronican)	C++20	10 / 100	64 ms	328 KiB

kronican

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define f first
#define s second
#define dbg(v) cerr << #v << " = " << v << "\n"
#define fall(i, s, n) for(int i=s; i<n; i++)
#define rfall(i, s, n) for(int i=s; i>=n; i--)

typedef pair<int, int> pii;
typedef tuple<int, int, int> trio;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 20+7;

int n, k;
vector<trio> ed;
int pai[MAXN];

int find(int v){
    return (v == pai[v] ? v : pai[v]=find(pai[v]));
}

void join(int x, int y){
    x = find(x), y = find(y);

    pai[y]=x;
}

int kr(int mask){
    int cost=0;

    int l;

    fall(i, 0, n) if((1<<i)&mask) l=i;

    fall(i, 0, n){
        if((1<<i)&mask) pai[i]=l;
        else pai[i]=i;
    }

    for(auto [w, x, y] : ed){
        x = find(x), y = find(y);

        if(x != y) join(x, y), cost += w;
    }

    return cost;
}

int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> n >> k;

    fall(i, 0, n)
    fall(j, 0, n){
        int w; cin >> w;

        ed.pb({w, j, i});
    }

    sort(ed.begin(), ed.end());

    int mn=1e9;

    fall(mask, 0, (1<<n)){
        if(__popcount(mask) != k) continue;

        mn = min(mn, kr(mask));
    }

    cout << mn << "\n";
}

• Subtask 1: 10 / 100