#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define rall(s) s.rbegin(), s.rend()
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define s second
#define f first
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const ll inf = 1e18, N = 1e5;
vector<pll> g[N];
pll fnd(int x, int n) {
priority_queue<pll> s;
vector<ll> d(n, inf);
d[x] = 0;
s.push({0, x});
int mx = x;
while (sz(s)) {
auto [dt, u] = s.top();
s.pop();
if (-dt != d[u]) continue;
if (d[u] > d[mx]) mx = u;
for (auto [to, w]: g[u]) {
if (d[to] > d[u] + w) {
d[to] = d[u] + w;
s.push({-d[to], to});
}
}
}
return {mx, d[mx]};
}
ll f(int n) {
int x = fnd(0, n).f;
return fnd(x, n).s;
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) {
for (int i = 0; i < n - 1; i++) {
g[i].push_back({i + 1, l[i]});
g[i + 1].push_back({i, l[i]});
}
for (int i = 0; i < n; i++) {
g[i].push_back({i + n, d[i]});
g[i + n].push_back({i, d[i]});
}
ll ans = inf;
for (int x = 0; x < n; x++) {
for (int y = x + 1; y < n; y++) {
g[x].push_back({y, c});
g[y].push_back({x, c});
ans = min(ans, f(2 * n));
g[x].pop_back();
g[y].pop_back();
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2904 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
1 ms |
2652 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
1 ms |
2652 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
1 ms |
2652 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
2652 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
2 ms |
2652 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
2652 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
2652 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
2652 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
2 ms |
2652 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
1 ms |
2652 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
1 ms |
2652 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
1 ms |
2652 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
1 ms |
2652 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
1 ms |
2652 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
1 ms |
2652 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
1 ms |
2652 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
2 ms |
2652 KB |
n = 10, 3189 is a correct answer |
19 |
Incorrect |
1 ms |
2652 KB |
n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2904 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
1 ms |
2652 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
1 ms |
2652 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
1 ms |
2652 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
2652 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
2 ms |
2652 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
2652 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
2652 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
2652 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
2 ms |
2652 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
1 ms |
2652 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
1 ms |
2652 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
1 ms |
2652 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
1 ms |
2652 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
1 ms |
2652 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
1 ms |
2652 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
1 ms |
2652 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
2 ms |
2652 KB |
n = 10, 3189 is a correct answer |
19 |
Incorrect |
1 ms |
2652 KB |
n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2904 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
1 ms |
2652 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
1 ms |
2652 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
1 ms |
2652 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
2652 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
2 ms |
2652 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
2652 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
2652 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
2652 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
2 ms |
2652 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
1 ms |
2652 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
1 ms |
2652 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
1 ms |
2652 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
1 ms |
2652 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
1 ms |
2652 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
1 ms |
2652 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
1 ms |
2652 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
2 ms |
2652 KB |
n = 10, 3189 is a correct answer |
19 |
Incorrect |
1 ms |
2652 KB |
n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2904 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
1 ms |
2652 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
1 ms |
2652 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
1 ms |
2652 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
2652 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
2 ms |
2652 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
2652 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
2652 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
2652 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
2 ms |
2652 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
1 ms |
2652 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
1 ms |
2652 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
1 ms |
2652 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
1 ms |
2652 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
1 ms |
2652 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
1 ms |
2652 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
1 ms |
2652 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
2 ms |
2652 KB |
n = 10, 3189 is a correct answer |
19 |
Incorrect |
1 ms |
2652 KB |
n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2904 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
1 ms |
2652 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
1 ms |
2652 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
1 ms |
2652 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
2652 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
2 ms |
2652 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
2652 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
2652 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
2652 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
2 ms |
2652 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
1 ms |
2652 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
1 ms |
2652 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
1 ms |
2652 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
1 ms |
2652 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
1 ms |
2652 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
1 ms |
2652 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
1 ms |
2652 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
2 ms |
2652 KB |
n = 10, 3189 is a correct answer |
19 |
Incorrect |
1 ms |
2652 KB |
n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2904 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
1 ms |
2652 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
1 ms |
2652 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
1 ms |
2652 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
2652 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
2 ms |
2652 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
2652 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
2652 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
2652 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
2 ms |
2652 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
1 ms |
2652 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
1 ms |
2652 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
1 ms |
2652 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
1 ms |
2652 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
1 ms |
2652 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
1 ms |
2652 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
1 ms |
2652 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
2 ms |
2652 KB |
n = 10, 3189 is a correct answer |
19 |
Incorrect |
1 ms |
2652 KB |
n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2904 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
1 ms |
2652 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
1 ms |
2652 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
1 ms |
2652 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
2652 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
2 ms |
2652 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
2652 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
2652 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
2652 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
2 ms |
2652 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
1 ms |
2652 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
1 ms |
2652 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
1 ms |
2652 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
1 ms |
2652 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
1 ms |
2652 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
1 ms |
2652 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
1 ms |
2652 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
2 ms |
2652 KB |
n = 10, 3189 is a correct answer |
19 |
Incorrect |
1 ms |
2652 KB |
n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2904 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
1 ms |
2652 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
1 ms |
2652 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
1 ms |
2652 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
2652 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
2 ms |
2652 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
2652 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
2652 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
2652 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
2 ms |
2652 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
1 ms |
2652 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
1 ms |
2652 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
1 ms |
2652 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
1 ms |
2652 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
1 ms |
2652 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
1 ms |
2652 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
1 ms |
2652 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
2 ms |
2652 KB |
n = 10, 3189 is a correct answer |
19 |
Incorrect |
1 ms |
2652 KB |
n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000 |
20 |
Halted |
0 ms |
0 KB |
- |