oj.uz

답안 #380271

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
380271 2021-03-20T18:53:16 Z ritul_kr_singh Kronican (COCI16_kronican) C++17
10 / 100
 219 ms 364 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'
 
vector<int> e;
int get(int u){
	return e[u] < 0 ? u : e[u] = get(e[u]);
}
bool unite(int u, int v){
	u = get(u), v = get(v);
	if(u==v) return false;
	if(e[u] > e[v]) swap(u, v);
	e[u] += e[v], e[v] = u;
	return true;
}
 
signed main(){
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int n, k; cin >> n >> k;
	int d[n][n];
	vector<array<int, 3>> edges;
	for(int i=0; i<n; ++i){
		for(int j=0; j<n; ++j){
			cin >> d[i][j];
		}
	}
	for(int i=0; i<n; ++i){
		for(int j=i+1; j<n; ++j){
			edges.push_back({min(d[i][j], d[j][i]), i, j});
		}
	}
	sort(edges.begin(), edges.end());
 
	int ans = 1e18;
	for(int i=0; i<(1<<n); ++i){
		int cnt = 0;
		for(int j=0; j<n; ++j) cnt += (bool)((1<<j)&i);
		if(cnt != k) continue;
		e.assign(n, -1);
		int first = -1, res = 0;
		for(int j=0; j<n; ++j) if((1<<j)&i) first = j;
		for(int j=0; j<n; ++j) if((1<<j)&i) unite(j, first);
		for(auto edge : edges){
			if(unite(edge[1], edge[2])) res += edge[0];
		}
		ans = min(ans, res);
	}
	cout << ans;
}

Subtask #1
10.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Incorrect 3 ms 364 KB Output isn't correct
6 Incorrect 3 ms 364 KB Output isn't correct
7 Incorrect 15 ms 364 KB Output isn't correct
8 Incorrect 27 ms 364 KB Output isn't correct
9 Incorrect 24 ms 364 KB Output isn't correct
10 Incorrect 219 ms 364 KB Output isn't correct