Submission #914149

#	Time	Username	Problem	Language	Result	Execution time	Memory
914149		lamter	Race (IOI11_race)	C++17	100 / 100	739 ms	48736 KiB

race

#include "race.h"
#include <bits/stdc++.h>

template <class Fun> class y_combinator_result {
	Fun fun_;

  public:
	template <class T>
	explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

	template <class... Args> decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};

template <class Fun> decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

struct Edge {
	int u, v, w;

	Edge(int _u = 0, int _v = 0, int _w = 0) : u(_u), v(_v), w(_w) {}
	int other(int x) const {
		//khong mot ai ngoai em
		return x ^ u ^ v;
	}
};

int best_path(int n, int k, int H[][2], int L[]) {
	std::vector <Edge> edges; edges.reserve(n - 1);
	std::vector <std::vector <int>> g(n);
	for (int i = 0; i < n - 1; i += 1) {
		int u = H[i][0], v = H[i][1], w = L[i];
		g[u].push_back(edges.size());
		g[v].push_back(edges.size());
		edges.emplace_back(u, v, w);
	}

	int ans = n + 1;
	std::vector <int> was(n), siz(n), lvl(n), dist(n);
	auto decompose = y_combinator([&] (auto decompose, int u) -> void {
		int sz = y_combinator([&] (auto dfs, int u, int p) -> int {
			int sz = 1;
			for (int id : g[u]) {
				int v = edges[id].other(u);
				if (v == p or was[v])
					continue;
				sz += dfs(v, u);
			}
			return siz[u] = sz;
		}) (u, u);
		auto centroid = y_combinator([&] (auto centroid, int u, int p) -> int {
			for (int id : g[u]) {
				int v = edges[id].other(u);
				if (v == p or was[v])
					continue;
				if (siz[v] > sz / 2)
					return centroid(v, u);
			}
			return u;
		});
		std::unordered_map <int, int> maps;

		auto chmin = [&] (int p, int x) -> void {
			auto it = maps.emplace(p, x);
			if (not it.second) {
				it.first->second = std::min(it.first->second, x);
			}
		};

		auto query = [&] (int p) -> int {
			auto it = maps.find(p);
			if (it == maps.end())
				return n + 1;
			return it->second;
		};

		int c = centroid(u, u);
		lvl[c] = 0;
		dist[c] = 0;
		auto upd = y_combinator([&] (auto dfs, int u, int p) -> void {
			for (int id : g[u]) {
				int v = edges[id].other(u);
				if (v == p or was[v])
					continue;
				if (dist[v] <= k) {
					dfs(v, u);
					chmin(dist[v], lvl[v]);
				}
			}
		});

		auto get = y_combinator([&] (auto dfs, int u, int p) -> void {
			for (int id : g[u]) {
				int v = edges[id].other(u);
				if (v == p or was[v])
					continue;
				lvl[v] = lvl[u] + 1;
				dist[v] = dist[u] + edges[id].w;
				if (dist[v] <= k) {
					dfs(v, u);
					ans = std::min(ans, lvl[v] + query(k - dist[v]));
				}
			}
		});

		for (int id : g[c]) {
			int x = edges[id].other(c);
			if (was[x])
				continue;
			lvl[x] = 1;
			dist[x] = edges[id].w;
			ans = std::min(ans, query(k - dist[x]) + 1);
			get(x, c);
			upd(x, c);
			chmin(dist[x], lvl[x]);
		}

		was[c] = 1;

		ans = std::min(ans, query(k));

		for (int id : g[c]) {
			int x = edges[id].other(c);
			if (was[x])
				continue;
			decompose(x);
		}
	});

	decompose(0);

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

int h[10000][2];
int l[10000];

#ifdef ILOVELAMTER
	int main(void) {
		h[0][0] = 0; h[0][1] = 1;
		h[1][0] = 1; h[1][1] = 2;
		h[2][0] = 1; h[2][1] = 3;
		l[0] = 1;
		l[1] = 2;
		l[2] = 4;
		std::cout << best_path(4, 3, h, l);
		return 0;
	}
#endif // ILOVELAMTER

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57