← Real problems

ucrpc21h

mediumgraphshortest-pathknapsackStatement on DMOJ

CP Lang

30 lines0.3 spec
// ucrpc21h: four couriers share round trips from the depot, each courier's day at most 600. A
// round trip to v costs 2 dist(v), so split the shortest distances into four loads of at most 300:
// a 3-D subset-sum over three loads, the fourth taking the rest.
const limit = 300
let (n, m) = read<(1..=100, 0..=10_000)>()
domain V = [n]
let roads = read<[m](u: V, v: V, w: 1..=1_000_000_000)>()
let paths = dijkstra(Graph.undirected(roads), from: [(V.first!, 0)])
fn busiest() -> ?Int:
    if roads.any(r => r.w > limit) or V.any(v => paths.dist[v] == None):
        return None
    let d = [V] v => paths.dist[v]!
    let total = d.sum()
    if d.max()! > limit or total > 4 * limit:
        return None
    domain Load = 0..=min(limit, total)
    domain Split = (Load, Load, Load)
    var can: [Split]Bool = false
    can[0, 0, 0] = true
    for v in V:
        if d[v] > 0:
            for (a, b, c) in Split.rev:
                for from in [(a - d[v], b, c), (a, b - d[v], c), (a, b, c - d[v])]:
                    if let p = Split.at(from):
                        can[a, b, c] = can[a, b, c] or can[p]
    Split.filter(p => can[p]).map(((a, b, c)) => max(max(a, b), max(c, total - a - b - c))).min()
if let day = busiest() and day <= limit:
    print(2 * day)
else:
    print("Impossible!")

Accepted C++

140 lines · 9.78 s on the judge
#include "bits/extc++.h"

using namespace std;

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

template <typename T, typename... 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

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

template <typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

const int maxm = 305, inf = 1e9;

int cur[maxm][maxm][maxm], pre[maxm][maxm][maxm];

long solve(vector<long> arr) {
	if (*max_element(begin(arr), end(arr)) > maxm ||
		accumulate(begin(arr), end(arr), long(0)) > maxm * 4) {
		return inf;
	}

	int n = sz(arr);
	vector<long> psum(n + 1);
	for (int i = 0; i < n; i++) {
		psum[i + 1] = psum[i] + arr[i];
	}
	int tmp[4];
	bool f = true;
	auto gprev = [&](int a, int b, int c, int d) -> int {
		if (max({a, b, c, d}) > maxm) {
			return inf;
		}
		if (f) {
			return max({a, b, c, d});
		}
		tmp[0] = a;
		tmp[1] = b;
		tmp[2] = c;
		tmp[3] = d;
		sort(begin(tmp), end(tmp));
		return pre[tmp[0]][tmp[1]][tmp[2]];
	};
	for (int i = n - 1; i >= 0; i--) {
		memset(cur, 0x3f, sizeof(cur));
		for (int a = 0; a < maxm; a++) {
			for (int b = a; b < maxm; b++) {
				for (int c = b; c < maxm; c++) {
					int d = psum[i] - a - b - c;
					if (c <= d) {
						int x = arr[i];
						cur[a][b][c] =
							min({gprev(a + x, b, c, d), gprev(a, b + x, c, d),
								 gprev(a, b, c + x, d), gprev(a, b, c, d + x)});
					}
				}
			}
		}
		memcpy(pre, cur, sizeof(cur));
		f = false;
	}
	return cur[0][0][0];
}

void solve() {
	int n, m;
	cin >> n >> m;
	vector<pair<int, long>> graph[n];
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		if (w > 300) {
			cout << "Impossible!" << endl;
			return;
		}
		graph[u].emplace_back(v, w);
		graph[v].emplace_back(u, w);
	}
	vector<long> dist(n);
	fill(begin(dist), end(dist), long(4e18));
	min_pq<pair<long, int>> pq;
	auto push = [&](int u, long d) -> void {
		if (d < dist[u]) {
			dist[u] = d;
			pq.emplace(d, u);
		}
	};
	push(0, 0);
	while (sz(pq)) {
		auto [d, u] = pq.top();
		pq.pop();
		for (auto& [v, w] : graph[u]) {
			push(v, d + w);
		}
	}
	assert(*max_element(begin(dist), end(dist)) < 4e18);
	long ans = solve(dist) * 2;
	if (ans <= 600) {
		cout << ans << endl;
	} else {
		cout << "Impossible!" << 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();
	}
}