oj.uz

Submission #612752

# Submission time Handle Problem Language Result Execution time Memory
612752 2022-07-29T23:59:37 Z Temmie Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 212 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -