Submission #1216085

#TimeUsernameProblemLanguageResultExecution timeMemory
1216085Rafael_AugustoKronican (COCI16_kronican)C++20
10 / 100
65 ms328 KiB
#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[x]=y; } 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"; }
#Verdict Execution timeMemoryGrader output
Fetching results...