#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define pll pair<long long, long long>
#define pii pair<int, int>
#include "shortcut.h"
using namespace std;
const ll INF = 1e18;
ll lencycle;
vector < vector <pair<int, ll> > > g;
vector <bool> cycle, vis;
pair<ll, int> dfs(int u, ll distc, ll curdist) {
ll tmp = curdist - distc;
if (cycle[u])
curdist = min(curdist, tmp + lencycle - distc);
vis[u] = true;
pair<ll, int> mx = {curdist, u};
for (auto to : g[u]) {
if (vis[to.fi])
continue;
if (cycle[u] && cycle[to.fi])
mx = max(mx, dfs(to.fi, distc + to.se, curdist + to.se));
else
mx = max(mx, dfs(to.fi, distc, curdist + to.se));
}
return mx;
}
ll case123(int n, vector <int> l1, vector <int> d1, int c1) {
ll ans = INF, c = 1ll * c1;
vector <ll> p(n), d(n), l(n);
for (int i = 0; i < n; i++)
d[i] = d1[i] * 1ll;
for (int i = 0; i < n; i++)
l[i] = l1[i] * 1ll;
p[0] = 0;
for (int i = 1; i < n; i++)
p[i] = p[i - 1] + l[i - 1];
ll maxdist = 0;
for (int k = 0; k < n - 1; k++)
for (int t = k + 1; t < n; t++) {
ll mind;
mind = p[t] - p[k];
maxdist = max(maxdist, mind + d[k] + d[t]);
}
ans = maxdist;
cycle.resize(2 * n);
vis.resize(2 * n);
g.resize(2 * n);
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
ll maxdist = 0;
// if (c >= p[j] - p[i])
// continue;
for (int k = 0; k < n; k++) {
g[k].clear();
g[k + n].clear();
vis[k + n] = vis[k] = false;
cycle[k + n] = cycle[k] = false;
}
for (int k = 0; k < n - 1; k++) {
g[k].pb({k + 1, l[k]});
g[k + 1].pb({k, l[k]});
}
for (int k = 0; k < n; k++) {
g[k].pb({n + k, d[k]});
g[n + k].pb({k, d[k]});
}
g[i].pb({j, c});
g[j].pb({i, c});
for (int k = i; k <= j; k++) {
cycle[k] = true;
}
lencycle = 0;
for (int k = i; k < j; k++)
lencycle += l[k];
lencycle += c;
pair<ll, int> tmp = dfs(0, 0, 0);
for (int k = 0; k < n; k++) {
vis[k] = vis[k + n] = false;
}
pair<ll, int> tmp1 = dfs(tmp.se, 0, 0);
// cout << "new edge " << i << " " << j << endl;
// cout << tmp.fi << " " << tmp.se << endl;
// cout << " " << tmp1.fi << " " << tmp1.se << endl;
// cout << endl;
ans = min(ans, tmp1.fi);
}
}
return ans;
}
ll find_shortcut(int n, vector <int> l, vector <int> d, int c) {
if (n <= 500)
return case123(n, l, d, c);
return 0ll;
}
Compilation message
shortcut.cpp: In function 'long long int case123(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:61:7: warning: unused variable 'maxdist' [-Wunused-variable]
61 | ll maxdist = 0;
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
1 ms |
256 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
1 ms |
256 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
1 ms |
256 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
1 ms |
256 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
1 ms |
256 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
1 ms |
256 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
1 ms |
256 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
1 ms |
256 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
