제출 #379835

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
379835		huynhtrankhanh	Race (IOI11_race)	C++17	100 / 100	563 ms	48236 KiB

race

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

int best_path(int n, int k, int h[][2], int l[])
{
	const int maxn = 200001;
	const int inf = 0x3f3f3f3f;

	vector<pair<int, int>> graph[maxn];

	for (int i = 0; i < n - 1; i++)
	{
		int u = h[i][0];
		int v = h[i][1];
		int w = l[i];

		graph[u].emplace_back(v, w);
		graph[v].emplace_back(u, w);
	}

	int size[maxn];
	bool ignored[maxn];
	memset(ignored, 0, sizeof(ignored));

	auto get_centroid = [&](int root) {
		{
			auto dfs = [&](auto dfs, int vertex, int parent) -> void {
				size[vertex] = 0;
				for (auto [adjacent, _]: graph[vertex])
					if (adjacent != parent) if (!ignored[adjacent])
					{
						dfs(dfs, adjacent, vertex);
						size[vertex] += size[adjacent];
					}

				size[vertex]++;
			};

			dfs(dfs, root, -1);
		}

		auto dfs = [&](auto dfs, int vertex, int parent) -> int {
			for (auto [adjacent, _]: graph[vertex])
				if (adjacent != parent) if (!ignored[adjacent])
				if (size[adjacent] > size[root] / 2)
					return dfs(dfs, adjacent, vertex);

			return vertex;
		};

		return dfs(dfs, root, -1);
	};

	const int maxk = 1000001;

	int depth[maxk];

	int counters[maxk];
	memset(counters, 0, sizeof(counters));
	int counter = 0;

	auto get = [&](int index) {
		if (index >= maxk) return inf;
		if (counters[index] == counter) return depth[index];
		return inf;
	};

	auto store = [&](int index, int value) {
		if (index >= maxk) return;
		counters[index] = counter;
		depth[index] = value;
	};

	auto clear = [&]() {
		counter++;
	};

	int result = inf;

	struct distance_t
	{
		int depth, distance;
	};

	distance_t distances[maxn];

	auto dfs = [&](auto dfs, int vertex) -> void {
		int centroid = get_centroid(vertex);
		ignored[centroid] = true;

		clear();

		store(0, 0);

		for (auto [adjacent, initial_edge]: graph[centroid])
		{
			if (ignored[adjacent]) continue;

			int counter = 0;
			auto dfs = [&](auto dfs, int vertex, int parent, int depth, int distance) -> void {
				auto clamp = [&](int x) {
					return min(inf, x);
				};

				distances[counter++] = { depth + 1, clamp(distance + initial_edge) };

				for (auto [adjacent, weight]: graph[vertex])
					if (adjacent != parent) if (!ignored[adjacent])
						dfs(dfs, adjacent, vertex, depth + 1, clamp(distance + weight));
			};


			dfs(dfs, adjacent, centroid, 0, 0);

			for (int i = 0; i < counter; i++)
			{
				auto &distance = distances[i];

				int companion = k - distance.distance;
				if (companion < 0) continue;

				result = min(result, get(companion) + distance.depth);
			}

			for (int i = 0; i < counter; i++)
			{
				auto &distance = distances[i];
				store(distance.distance, min(get(distance.distance), distance.depth));
			}
		}

		for (auto [adjacent, _]: graph[centroid])
			if (!ignored[adjacent])
				dfs(dfs, adjacent);
	};

	dfs(dfs, 0);

	return result == inf ? -1 : result;
}

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