Submission #492071

#	Time	Username	Problem	Language	Result	Execution time	Memory
492071		Virv	Dreaming (IOI13_dreaming)	C++17	0 / 100	45 ms	6676 KiB

dreaming

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

#include "dreaming.h"

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, INT_MAX / 2);

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

	auto const wc = [&](int i) {
		dfs(i);
		int R = D[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];
		}
	};

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

	int R{};
	if (C.size() >= 1) R = std::max(R, C[0]);
	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);
	return R;
}

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