Submission #259879

#	Time	Username	Problem	Language	Result	Execution time	Memory
259879		islingr	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

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

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define eb(x...) emplace_back(x)

bool ckmin(auto &a, const auto &b) { return a > b ? a = b, 1 : 0; }

int best_path(int n, int k, int h[][2], int l[]) {
	vector<bool> dead(n);
	vector<int> mn(k + 1), sz(n);
	vector<vector<pair<int, int>>> g(n);

	rep(e, 0, n - 1) {
		g[h[e][0]].eb(h[e][1], l[e]);
		g[h[e][1]].eb(h[e][0], l[e]);
	}

	int ans = n;

	function<void(int, int)> init = [&](int u, int p) {
		sz[u] = 1;
		for (auto &[v, d] : g[u])
			if (v != p && !dead[v])
				init(v, u), sz[u] += sz[v];
	};

	function<int(int, int)> centroid = [&](int u, int p) {
		for (auto &[v, d] : g[u])
			if (v != p && !dead[v] && 2 * sz[v] > sz[root])
				return centroid(v, u);
		return u;
	};

	function<void(int)> solve = [&](int root) {
		init(root, -1); root = centroid(root, -1);

		function<void(int, int, int)> clear = [&](int u, int p, int dist) {
			if (dist > k) return;
			mn[dist] = mn[k - dist] = n;
			for (auto &[v, d] : g[u])
				if (v != p && !dead[v])
					clear(v, u, dist + d);
		};
		clear(root, -1, 0);

		vector<pair<int, int>> lazy; int dep = 0;
		function<void(int, int, int)> dfs = [&](int u, int p, int dist) {
			if (dist > k) return;
			ckmin(ans, dep + mn[k - dist]);
			lazy.eb(dist, dep++);
			for (auto &[v, d] : g[u]) {
				if (v == p || dead[v]) continue;
				dfs(v, u, dist + d);
				if (u != root) continue;
				for (auto &[dist, dep] : lazy) ckmin(mn[dist], dep);
				lazy.clear();
			}
			--dep;
		};
		mn[0] = 0; dfs(root, -1, 0);

		dead[root] = true;
		for (auto &[v, d] : g[root]) if (!dead[v]) solve(v);
	};
	solve(0);

	return ans != n ? ans : -1;
}

Compilation message (stderr)

race.cpp: In lambda function:
race.cpp:23:19: warning: unused variable 'd' [-Wunused-variable]
   for (auto &[v, d] : g[u])
                   ^
race.cpp: In lambda function:
race.cpp:30:45: error: 'root' was not declared in this scope
    if (v != p && !dead[v] && 2 * sz[v] > sz[root])
                                             ^~~~
race.cpp:30:45: note: suggested alternative: 'rint'
    if (v != p && !dead[v] && 2 * sz[v] > sz[root])
                                             ^~~~
                                             rint
race.cpp:29:19: warning: unused variable 'd' [-Wunused-variable]
   for (auto &[v, d] : g[u])
                   ^
race.cpp: In lambda function:
race.cpp:64:19: warning: unused variable 'd' [-Wunused-variable]
   for (auto &[v, d] : g[root]) if (!dead[v]) solve(v);
                   ^