Submission #492099

#	Time	Username	Problem	Language	Result	Execution time	Memory
492099		Virv	Dreaming (IOI13_dreaming)	C++17	100 / 100	75 ms	14660 KiB

dreaming

#include <algorithm>
#include <climits>
#include <functional>
#include <iostream>
#include <vector>

#include "dreaming.h"

constexpr int INF = INT_MAX / 2;

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	std::vector<std::vector<std::pair<int, int>>> G(N);
	for (int i{}; i < M; ++i) {
		G[A[i]].emplace_back(B[i], T[i]);
		G[B[i]].emplace_back(A[i], T[i]);
	}

	std::vector<int> D(N, INF);

	std::function<int(int)> dfs = [&](int i) {
		auto &d = D[i] = 0;
		for (auto &[u, w] : G[i])
			if (D[u] == INF) d = std::max(d, dfs(u) + w);
		return d;
	};

	auto const wc = [&](int i) {
		int R = dfs(i);
		for (;;) {
			int c = N;
			int p = 0;
			int q = 0;
			D[i]  = 0;

			for (auto [u, w] : G[i]) {
				auto d = w + D[u];
				if (d >= p) {
					std::swap(u, c);
					std::swap(d, p);
					std::swap(w, q);
				}

				D[i] = std::max(D[i], d);
			}

			if (c == N) return R;

			D[c] = std::max(D[c], D[i] + q);
			i	 = c;

			if (D[i] >= R) return R;
			R = D[i];
		}
	};

	auto const diam = [&](int start) {
		std::vector<int> Q{start};
		D[start] = 0;

		for (size_t i{}; i < Q.size(); ++i) {
			auto v = Q[i];
			for (auto [u, w] : G[v])
				if (D[v] + w < D[u]) {
					D[u] = D[v] + w;
					Q.push_back(u);
				}
		}

		auto m = *max_element(Q.begin(), Q.end(), [&](auto a, auto b) { return D[a] < D[b]; });
		for (auto q : Q) D[q] = INF;
		Q.push_back(m);
		D[m] = 0;

		for (size_t i{}; i < Q.size(); ++i) {
			auto v = Q[i];
			for (auto [u, w] : G[v])
				if (D[v] + w < D[u]) {
					D[u] = D[v] + w;
					Q.push_back(u);
				}
		}

		m = *max_element(Q.begin(), Q.end(), [&](auto a, auto b) { return D[a] < D[b]; });
		return D[m];
	};

	std::vector<int> C;
	for (int i{}; i < N; ++i)
		if (D[i] == INF) C.push_back(wc(i));
	sort(C.begin(), C.end(), std::greater{});

	int R{};
	if (C.size() >= 2) R = std::max(R, C[0] + C[1] + L);
	if (C.size() >= 3) R = std::max(R, C[1] + C[2] + L + L);

	D.assign(N, INF);
	for (int i{}; i < N; ++i)
		if (D[i] == INF) R = std::max(R, diam(i));
	return R;
}

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23