oj.uz

Submission #492071

# Submission time Handle Problem Language Result Execution time Memory
492071 2021-12-05T11:19:07 Z Virv Dreaming (IOI13_dreaming) C++17
0 / 100
 45 ms 6676 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 6676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 6676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 5096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 6676 KB Output isn't correct
2 Halted 0 ms 0 KB -