Submission #296149

#	Time	Username	Problem	Language	Result	Execution time	Memory
296149		RealSuperman1	Shortcut (IOI16_shortcut)	C++14	0 / 100	1 ms	256 KiB

shortcut

#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 (stderr)

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;
      |       ^~~~~~~

• 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