← Real problems

noi15p4

mediumgreedyhuffmanheapStatement on DMOJ

CP Lang

14 lines0.3 spec
// NOI 2015 "Homer's Epic": k-ary Huffman code, minimizing total length and then
// the longest word. Pad with weight-0 leaves so every merge takes exactly k.
let (n, k) = read<(1..=1e5, 2..=9)>()
let w = read<[n]0..=1e11>()
let pad = (k - 1 - (n - 1) % (k - 1)) % (k - 1)
var heap = MinHeap.of(w.map(x => (w: x, depth: 0)).collect() + [(w: 0, depth: 0) for _ in 0..pad])
var total = 0
while heap.len > 1:
    let kids = [heap.pop()! for _ in 0..k]
    let merged = (w: kids.sum(of: .w), depth: kids.max(of: .depth) + 1)
    total += merged.w
    heap.push(merged)
print(total)
print(heap.pop()!.depth)

Accepted C++

85 lines · 0.25 s on the judge
#include "bits/extc++.h"

using namespace std;

template<class T>
using mpq = priority_queue<T, vector<T>, greater<>>;

template<class T, class U = less<T>>
using rt = __gnu_pbds::tree<T, __gnu_pbds::null_type, U, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

template<class T>
void dbgh(const T &t) {
	cerr << t << endl;
}

template<class T, class ...U>
void dbgh(const T &t, const U &...u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...) cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" << ": "; dbgh(__VA_ARGS__)
#else
#define cerr if(false) cerr
#define dbg(...) 1412
#endif

//imagine a language where int = long
#define long int64_t

//typing too hard
#define endl "\n"

#define sz(x) static_cast<int>((x).size())

#define inline inline __attribute__((always_inline))

void solve() {
	int n, k;
	cin >> n >> k;
	mpq<pair<long, int>> pq;
	for(int i = 0; i < n; i++) {
		long x;
		cin >> x;
		pq.emplace(x, 0);
	}
	if(k != 2) {
		while(sz(pq) % (k - 1) != 1) {
			pq.emplace(0, 0);
		}
	}
	long cans = 0;
	while(sz(pq) > 1) {
		long ans = 0;
		int mans = 0;
		for(int i = 0; i < k && sz(pq); i++) {
			auto[x, d] = pq.top();
			pq.pop();
			ans += x;
			mans = max(mans, d);
		}
		cans += ans;
		pq.emplace(ans, mans + 1);
	}
	auto[x, d] = pq.top();
	pq.pop();
	cout << cans << endl;
	cout << d << endl;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::failbit);
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
	int t = 1;
//	cin >> t;
	for(int _ = 1; _ <= t; _++) {
		dbg(_);
//		cout << "Case #" << _ << ": ";
		solve();
	}
}