Submission #612752

#	Time	Username	Problem	Language	Result	Execution time	Memory
612752		Temmie	Shortcut (IOI16_shortcut)	C++17	0 / 100	1 ms	212 KiB

shortcut

#include <bits/stdc++.h>

long long find_shortcut(int n, std::vector <int> l, std::vector <int> d, int c) {
	long long ans = 1LL << 60;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			long long val = std::max(d[0], d[n - 1]);
			for (int start : { 0, n - 1 }) {
				std::vector <bool> vis(n, false);
				std::vector <std::map <int, long long>> mp(n);
				auto dfs = [&] (auto&& self, int node, int root, long long wei) -> void {
					if (vis[node]) {
						return;
					}
					vis[node] = true;
					auto it = mp[node].find(root);
					if (it == mp[node].end()) mp[node][root] = wei + d[node];
					else it->second = std::min(it->second, wei + d[node]);
					if ((long long) d[node] > wei) {
						root = node;
						wei = d[node];
					}
					if (node) self(self, node - 1, root, wei + l[node - 1]);
					if (node + 1 < n) self(self, node + 1, root, wei + l[node]);
					if (node == i) self(self, j, root, wei + c);
					if (node == j) self(self, i, root, wei + c);
					vis[node] = false;
				};
				dfs(dfs, 0, 0, d[0]);
				dfs(dfs, n - 1, n - 1, d[n - 1]);
				for (const auto& map : mp) {
					for (auto p : map) {
						val = std::max(val, p.second);
					}
				}
			}
			ans = std::min(ans, val);
		}
	}
	return ans;
}

Compilation message (stderr)

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:8:13: warning: unused variable 'start' [-Wunused-variable]
    8 |    for (int start : { 0, n - 1 }) {
      |             ^~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3