# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1020521 | 2024-07-12T06:29:34 Z | vjudge1 | Shortcut (IOI16_shortcut) | C++17 | 1 ms | 348 KB |
#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 = 100; 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) { ll res = 0; for (int i = 0; i < n; i++) { res = max(res, fnd(i, n).s); } return res; } long long find_shortcut(int n, vector<int> l, 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 | 0 ms | 344 KB | n = 4, 80 is a correct answer |
2 | Correct | 0 ms | 348 KB | n = 9, 110 is a correct answer |
3 | Correct | 0 ms | 348 KB | n = 4, 21 is a correct answer |
4 | Correct | 0 ms | 348 KB | n = 3, 4 is a correct answer |
5 | Correct | 0 ms | 348 KB | n = 2, 62 is a correct answer |
6 | Correct | 0 ms | 348 KB | n = 2, 3 is a correct answer |
7 | Correct | 0 ms | 348 KB | n = 3, 29 is a correct answer |
8 | Correct | 0 ms | 348 KB | n = 2, 3 is a correct answer |
9 | Correct | 0 ms | 348 KB | n = 2, 3 is a correct answer |
10 | Correct | 0 ms | 348 KB | n = 2, 2000000001 is a correct answer |
11 | Correct | 0 ms | 348 KB | n = 2, 3000000000 is a correct answer |
12 | Correct | 0 ms | 348 KB | n = 3, 3000000000 is a correct answer |
13 | Correct | 0 ms | 348 KB | n = 3, 3000000000 is a correct answer |
14 | Correct | 0 ms | 348 KB | n = 4, 3000000001 is a correct answer |
15 | Correct | 0 ms | 348 KB | n = 4, 4000000000 is a correct answer |
16 | Correct | 0 ms | 348 KB | n = 5, 4000000000 is a correct answer |
17 | Correct | 1 ms | 348 KB | n = 10, 1000000343 is a correct answer |
18 | Correct | 1 ms | 348 KB | n = 10, 3189 is a correct answer |
19 | Correct | 1 ms | 348 KB | n = 10, 7000000000 is a correct answer |
20 | Correct | 0 ms | 348 KB | n = 5, 12 is a correct answer |
21 | Correct | 0 ms | 348 KB | n = 5, 25 is a correct answer |
22 | Correct | 0 ms | 348 KB | n = 2, 122 is a correct answer |
23 | Correct | 1 ms | 348 KB | n = 10, 117 is a correct answer |
24 | Correct | 1 ms | 348 KB | n = 10, 336 is a correct answer |
25 | Correct | 1 ms | 348 KB | n = 10, 438 is a correct answer |
26 | Correct | 1 ms | 348 KB | n = 10, 206 is a correct answer |
27 | Correct | 1 ms | 348 KB | n = 10, 636 is a correct answer |
28 | Correct | 1 ms | 348 KB | n = 4, 2399 is a correct answer |
29 | Correct | 1 ms | 348 KB | n = 10, 10992 is a correct answer |
30 | Correct | 1 ms | 348 KB | n = 10, 3112 is a correct answer |
31 | Runtime error | 0 ms | 348 KB | Execution killed with signal 11 |
32 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | n = 4, 80 is a correct answer |
2 | Correct | 0 ms | 348 KB | n = 9, 110 is a correct answer |
3 | Correct | 0 ms | 348 KB | n = 4, 21 is a correct answer |
4 | Correct | 0 ms | 348 KB | n = 3, 4 is a correct answer |
5 | Correct | 0 ms | 348 KB | n = 2, 62 is a correct answer |
6 | Correct | 0 ms | 348 KB | n = 2, 3 is a correct answer |
7 | Correct | 0 ms | 348 KB | n = 3, 29 is a correct answer |
8 | Correct | 0 ms | 348 KB | n = 2, 3 is a correct answer |
9 | Correct | 0 ms | 348 KB | n = 2, 3 is a correct answer |
10 | Correct | 0 ms | 348 KB | n = 2, 2000000001 is a correct answer |
11 | Correct | 0 ms | 348 KB | n = 2, 3000000000 is a correct answer |
12 | Correct | 0 ms | 348 KB | n = 3, 3000000000 is a correct answer |
13 | Correct | 0 ms | 348 KB | n = 3, 3000000000 is a correct answer |
14 | Correct | 0 ms | 348 KB | n = 4, 3000000001 is a correct answer |
15 | Correct | 0 ms | 348 KB | n = 4, 4000000000 is a correct answer |
16 | Correct | 0 ms | 348 KB | n = 5, 4000000000 is a correct answer |
17 | Correct | 1 ms | 348 KB | n = 10, 1000000343 is a correct answer |
18 | Correct | 1 ms | 348 KB | n = 10, 3189 is a correct answer |
19 | Correct | 1 ms | 348 KB | n = 10, 7000000000 is a correct answer |
20 | Correct | 0 ms | 348 KB | n = 5, 12 is a correct answer |
21 | Correct | 0 ms | 348 KB | n = 5, 25 is a correct answer |
22 | Correct | 0 ms | 348 KB | n = 2, 122 is a correct answer |
23 | Correct | 1 ms | 348 KB | n = 10, 117 is a correct answer |
24 | Correct | 1 ms | 348 KB | n = 10, 336 is a correct answer |
25 | Correct | 1 ms | 348 KB | n = 10, 438 is a correct answer |
26 | Correct | 1 ms | 348 KB | n = 10, 206 is a correct answer |
27 | Correct | 1 ms | 348 KB | n = 10, 636 is a correct answer |
28 | Correct | 1 ms | 348 KB | n = 4, 2399 is a correct answer |
29 | Correct | 1 ms | 348 KB | n = 10, 10992 is a correct answer |
30 | Correct | 1 ms | 348 KB | n = 10, 3112 is a correct answer |
31 | Runtime error | 0 ms | 348 KB | Execution killed with signal 11 |
32 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | n = 4, 80 is a correct answer |
2 | Correct | 0 ms | 348 KB | n = 9, 110 is a correct answer |
3 | Correct | 0 ms | 348 KB | n = 4, 21 is a correct answer |
4 | Correct | 0 ms | 348 KB | n = 3, 4 is a correct answer |
5 | Correct | 0 ms | 348 KB | n = 2, 62 is a correct answer |
6 | Correct | 0 ms | 348 KB | n = 2, 3 is a correct answer |
7 | Correct | 0 ms | 348 KB | n = 3, 29 is a correct answer |
8 | Correct | 0 ms | 348 KB | n = 2, 3 is a correct answer |
9 | Correct | 0 ms | 348 KB | n = 2, 3 is a correct answer |
10 | Correct | 0 ms | 348 KB | n = 2, 2000000001 is a correct answer |
11 | Correct | 0 ms | 348 KB | n = 2, 3000000000 is a correct answer |
12 | Correct | 0 ms | 348 KB | n = 3, 3000000000 is a correct answer |
13 | Correct | 0 ms | 348 KB | n = 3, 3000000000 is a correct answer |
14 | Correct | 0 ms | 348 KB | n = 4, 3000000001 is a correct answer |
15 | Correct | 0 ms | 348 KB | n = 4, 4000000000 is a correct answer |
16 | Correct | 0 ms | 348 KB | n = 5, 4000000000 is a correct answer |
17 | Correct | 1 ms | 348 KB | n = 10, 1000000343 is a correct answer |
18 | Correct | 1 ms | 348 KB | n = 10, 3189 is a correct answer |
19 | Correct | 1 ms | 348 KB | n = 10, 7000000000 is a correct answer |
20 | Correct | 0 ms | 348 KB | n = 5, 12 is a correct answer |
21 | Correct | 0 ms | 348 KB | n = 5, 25 is a correct answer |
22 | Correct | 0 ms | 348 KB | n = 2, 122 is a correct answer |
23 | Correct | 1 ms | 348 KB | n = 10, 117 is a correct answer |
24 | Correct | 1 ms | 348 KB | n = 10, 336 is a correct answer |
25 | Correct | 1 ms | 348 KB | n = 10, 438 is a correct answer |
26 | Correct | 1 ms | 348 KB | n = 10, 206 is a correct answer |
27 | Correct | 1 ms | 348 KB | n = 10, 636 is a correct answer |
28 | Correct | 1 ms | 348 KB | n = 4, 2399 is a correct answer |
29 | Correct | 1 ms | 348 KB | n = 10, 10992 is a correct answer |
30 | Correct | 1 ms | 348 KB | n = 10, 3112 is a correct answer |
31 | Runtime error | 0 ms | 348 KB | Execution killed with signal 11 |
32 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | n = 4, 80 is a correct answer |
2 | Correct | 0 ms | 348 KB | n = 9, 110 is a correct answer |
3 | Correct | 0 ms | 348 KB | n = 4, 21 is a correct answer |
4 | Correct | 0 ms | 348 KB | n = 3, 4 is a correct answer |
5 | Correct | 0 ms | 348 KB | n = 2, 62 is a correct answer |
6 | Correct | 0 ms | 348 KB | n = 2, 3 is a correct answer |
7 | Correct | 0 ms | 348 KB | n = 3, 29 is a correct answer |
8 | Correct | 0 ms | 348 KB | n = 2, 3 is a correct answer |
9 | Correct | 0 ms | 348 KB | n = 2, 3 is a correct answer |
10 | Correct | 0 ms | 348 KB | n = 2, 2000000001 is a correct answer |
11 | Correct | 0 ms | 348 KB | n = 2, 3000000000 is a correct answer |
12 | Correct | 0 ms | 348 KB | n = 3, 3000000000 is a correct answer |
13 | Correct | 0 ms | 348 KB | n = 3, 3000000000 is a correct answer |
14 | Correct | 0 ms | 348 KB | n = 4, 3000000001 is a correct answer |
15 | Correct | 0 ms | 348 KB | n = 4, 4000000000 is a correct answer |
16 | Correct | 0 ms | 348 KB | n = 5, 4000000000 is a correct answer |
17 | Correct | 1 ms | 348 KB | n = 10, 1000000343 is a correct answer |
18 | Correct | 1 ms | 348 KB | n = 10, 3189 is a correct answer |
19 | Correct | 1 ms | 348 KB | n = 10, 7000000000 is a correct answer |
20 | Correct | 0 ms | 348 KB | n = 5, 12 is a correct answer |
21 | Correct | 0 ms | 348 KB | n = 5, 25 is a correct answer |
22 | Correct | 0 ms | 348 KB | n = 2, 122 is a correct answer |
23 | Correct | 1 ms | 348 KB | n = 10, 117 is a correct answer |
24 | Correct | 1 ms | 348 KB | n = 10, 336 is a correct answer |
25 | Correct | 1 ms | 348 KB | n = 10, 438 is a correct answer |
26 | Correct | 1 ms | 348 KB | n = 10, 206 is a correct answer |
27 | Correct | 1 ms | 348 KB | n = 10, 636 is a correct answer |
28 | Correct | 1 ms | 348 KB | n = 4, 2399 is a correct answer |
29 | Correct | 1 ms | 348 KB | n = 10, 10992 is a correct answer |
30 | Correct | 1 ms | 348 KB | n = 10, 3112 is a correct answer |
31 | Runtime error | 0 ms | 348 KB | Execution killed with signal 11 |
32 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | n = 4, 80 is a correct answer |
2 | Correct | 0 ms | 348 KB | n = 9, 110 is a correct answer |
3 | Correct | 0 ms | 348 KB | n = 4, 21 is a correct answer |
4 | Correct | 0 ms | 348 KB | n = 3, 4 is a correct answer |
5 | Correct | 0 ms | 348 KB | n = 2, 62 is a correct answer |
6 | Correct | 0 ms | 348 KB | n = 2, 3 is a correct answer |
7 | Correct | 0 ms | 348 KB | n = 3, 29 is a correct answer |
8 | Correct | 0 ms | 348 KB | n = 2, 3 is a correct answer |
9 | Correct | 0 ms | 348 KB | n = 2, 3 is a correct answer |
10 | Correct | 0 ms | 348 KB | n = 2, 2000000001 is a correct answer |
11 | Correct | 0 ms | 348 KB | n = 2, 3000000000 is a correct answer |
12 | Correct | 0 ms | 348 KB | n = 3, 3000000000 is a correct answer |
13 | Correct | 0 ms | 348 KB | n = 3, 3000000000 is a correct answer |
14 | Correct | 0 ms | 348 KB | n = 4, 3000000001 is a correct answer |
15 | Correct | 0 ms | 348 KB | n = 4, 4000000000 is a correct answer |
16 | Correct | 0 ms | 348 KB | n = 5, 4000000000 is a correct answer |
17 | Correct | 1 ms | 348 KB | n = 10, 1000000343 is a correct answer |
18 | Correct | 1 ms | 348 KB | n = 10, 3189 is a correct answer |
19 | Correct | 1 ms | 348 KB | n = 10, 7000000000 is a correct answer |
20 | Correct | 0 ms | 348 KB | n = 5, 12 is a correct answer |
21 | Correct | 0 ms | 348 KB | n = 5, 25 is a correct answer |
22 | Correct | 0 ms | 348 KB | n = 2, 122 is a correct answer |
23 | Correct | 1 ms | 348 KB | n = 10, 117 is a correct answer |
24 | Correct | 1 ms | 348 KB | n = 10, 336 is a correct answer |
25 | Correct | 1 ms | 348 KB | n = 10, 438 is a correct answer |
26 | Correct | 1 ms | 348 KB | n = 10, 206 is a correct answer |
27 | Correct | 1 ms | 348 KB | n = 10, 636 is a correct answer |
28 | Correct | 1 ms | 348 KB | n = 4, 2399 is a correct answer |
29 | Correct | 1 ms | 348 KB | n = 10, 10992 is a correct answer |
30 | Correct | 1 ms | 348 KB | n = 10, 3112 is a correct answer |
31 | Runtime error | 0 ms | 348 KB | Execution killed with signal 11 |
32 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | n = 4, 80 is a correct answer |
2 | Correct | 0 ms | 348 KB | n = 9, 110 is a correct answer |
3 | Correct | 0 ms | 348 KB | n = 4, 21 is a correct answer |
4 | Correct | 0 ms | 348 KB | n = 3, 4 is a correct answer |
5 | Correct | 0 ms | 348 KB | n = 2, 62 is a correct answer |
6 | Correct | 0 ms | 348 KB | n = 2, 3 is a correct answer |
7 | Correct | 0 ms | 348 KB | n = 3, 29 is a correct answer |
8 | Correct | 0 ms | 348 KB | n = 2, 3 is a correct answer |
9 | Correct | 0 ms | 348 KB | n = 2, 3 is a correct answer |
10 | Correct | 0 ms | 348 KB | n = 2, 2000000001 is a correct answer |
11 | Correct | 0 ms | 348 KB | n = 2, 3000000000 is a correct answer |
12 | Correct | 0 ms | 348 KB | n = 3, 3000000000 is a correct answer |
13 | Correct | 0 ms | 348 KB | n = 3, 3000000000 is a correct answer |
14 | Correct | 0 ms | 348 KB | n = 4, 3000000001 is a correct answer |
15 | Correct | 0 ms | 348 KB | n = 4, 4000000000 is a correct answer |
16 | Correct | 0 ms | 348 KB | n = 5, 4000000000 is a correct answer |
17 | Correct | 1 ms | 348 KB | n = 10, 1000000343 is a correct answer |
18 | Correct | 1 ms | 348 KB | n = 10, 3189 is a correct answer |
19 | Correct | 1 ms | 348 KB | n = 10, 7000000000 is a correct answer |
20 | Correct | 0 ms | 348 KB | n = 5, 12 is a correct answer |
21 | Correct | 0 ms | 348 KB | n = 5, 25 is a correct answer |
22 | Correct | 0 ms | 348 KB | n = 2, 122 is a correct answer |
23 | Correct | 1 ms | 348 KB | n = 10, 117 is a correct answer |
24 | Correct | 1 ms | 348 KB | n = 10, 336 is a correct answer |
25 | Correct | 1 ms | 348 KB | n = 10, 438 is a correct answer |
26 | Correct | 1 ms | 348 KB | n = 10, 206 is a correct answer |
27 | Correct | 1 ms | 348 KB | n = 10, 636 is a correct answer |
28 | Correct | 1 ms | 348 KB | n = 4, 2399 is a correct answer |
29 | Correct | 1 ms | 348 KB | n = 10, 10992 is a correct answer |
30 | Correct | 1 ms | 348 KB | n = 10, 3112 is a correct answer |
31 | Runtime error | 0 ms | 348 KB | Execution killed with signal 11 |
32 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | n = 4, 80 is a correct answer |
2 | Correct | 0 ms | 348 KB | n = 9, 110 is a correct answer |
3 | Correct | 0 ms | 348 KB | n = 4, 21 is a correct answer |
4 | Correct | 0 ms | 348 KB | n = 3, 4 is a correct answer |
5 | Correct | 0 ms | 348 KB | n = 2, 62 is a correct answer |
6 | Correct | 0 ms | 348 KB | n = 2, 3 is a correct answer |
7 | Correct | 0 ms | 348 KB | n = 3, 29 is a correct answer |
8 | Correct | 0 ms | 348 KB | n = 2, 3 is a correct answer |
9 | Correct | 0 ms | 348 KB | n = 2, 3 is a correct answer |
10 | Correct | 0 ms | 348 KB | n = 2, 2000000001 is a correct answer |
11 | Correct | 0 ms | 348 KB | n = 2, 3000000000 is a correct answer |
12 | Correct | 0 ms | 348 KB | n = 3, 3000000000 is a correct answer |
13 | Correct | 0 ms | 348 KB | n = 3, 3000000000 is a correct answer |
14 | Correct | 0 ms | 348 KB | n = 4, 3000000001 is a correct answer |
15 | Correct | 0 ms | 348 KB | n = 4, 4000000000 is a correct answer |
16 | Correct | 0 ms | 348 KB | n = 5, 4000000000 is a correct answer |
17 | Correct | 1 ms | 348 KB | n = 10, 1000000343 is a correct answer |
18 | Correct | 1 ms | 348 KB | n = 10, 3189 is a correct answer |
19 | Correct | 1 ms | 348 KB | n = 10, 7000000000 is a correct answer |
20 | Correct | 0 ms | 348 KB | n = 5, 12 is a correct answer |
21 | Correct | 0 ms | 348 KB | n = 5, 25 is a correct answer |
22 | Correct | 0 ms | 348 KB | n = 2, 122 is a correct answer |
23 | Correct | 1 ms | 348 KB | n = 10, 117 is a correct answer |
24 | Correct | 1 ms | 348 KB | n = 10, 336 is a correct answer |
25 | Correct | 1 ms | 348 KB | n = 10, 438 is a correct answer |
26 | Correct | 1 ms | 348 KB | n = 10, 206 is a correct answer |
27 | Correct | 1 ms | 348 KB | n = 10, 636 is a correct answer |
28 | Correct | 1 ms | 348 KB | n = 4, 2399 is a correct answer |
29 | Correct | 1 ms | 348 KB | n = 10, 10992 is a correct answer |
30 | Correct | 1 ms | 348 KB | n = 10, 3112 is a correct answer |
31 | Runtime error | 0 ms | 348 KB | Execution killed with signal 11 |
32 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | n = 4, 80 is a correct answer |
2 | Correct | 0 ms | 348 KB | n = 9, 110 is a correct answer |
3 | Correct | 0 ms | 348 KB | n = 4, 21 is a correct answer |
4 | Correct | 0 ms | 348 KB | n = 3, 4 is a correct answer |
5 | Correct | 0 ms | 348 KB | n = 2, 62 is a correct answer |
6 | Correct | 0 ms | 348 KB | n = 2, 3 is a correct answer |
7 | Correct | 0 ms | 348 KB | n = 3, 29 is a correct answer |
8 | Correct | 0 ms | 348 KB | n = 2, 3 is a correct answer |
9 | Correct | 0 ms | 348 KB | n = 2, 3 is a correct answer |
10 | Correct | 0 ms | 348 KB | n = 2, 2000000001 is a correct answer |
11 | Correct | 0 ms | 348 KB | n = 2, 3000000000 is a correct answer |
12 | Correct | 0 ms | 348 KB | n = 3, 3000000000 is a correct answer |
13 | Correct | 0 ms | 348 KB | n = 3, 3000000000 is a correct answer |
14 | Correct | 0 ms | 348 KB | n = 4, 3000000001 is a correct answer |
15 | Correct | 0 ms | 348 KB | n = 4, 4000000000 is a correct answer |
16 | Correct | 0 ms | 348 KB | n = 5, 4000000000 is a correct answer |
17 | Correct | 1 ms | 348 KB | n = 10, 1000000343 is a correct answer |
18 | Correct | 1 ms | 348 KB | n = 10, 3189 is a correct answer |
19 | Correct | 1 ms | 348 KB | n = 10, 7000000000 is a correct answer |
20 | Correct | 0 ms | 348 KB | n = 5, 12 is a correct answer |
21 | Correct | 0 ms | 348 KB | n = 5, 25 is a correct answer |
22 | Correct | 0 ms | 348 KB | n = 2, 122 is a correct answer |
23 | Correct | 1 ms | 348 KB | n = 10, 117 is a correct answer |
24 | Correct | 1 ms | 348 KB | n = 10, 336 is a correct answer |
25 | Correct | 1 ms | 348 KB | n = 10, 438 is a correct answer |
26 | Correct | 1 ms | 348 KB | n = 10, 206 is a correct answer |
27 | Correct | 1 ms | 348 KB | n = 10, 636 is a correct answer |
28 | Correct | 1 ms | 348 KB | n = 4, 2399 is a correct answer |
29 | Correct | 1 ms | 348 KB | n = 10, 10992 is a correct answer |
30 | Correct | 1 ms | 348 KB | n = 10, 3112 is a correct answer |
31 | Runtime error | 0 ms | 348 KB | Execution killed with signal 11 |
32 | Halted | 0 ms | 0 KB | - |