oj.uz

답안 #296149

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
296149 2020-09-10T10:46:02 Z RealSuperman1 Shortcut (IOI16_shortcut) C++14
0 / 100
 1 ms 256 KB 
#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;
      |       ^~~~~~~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 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 -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 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 -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 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 -

Subtask #4
0 / 7.0

# 결과 실행 시간 메모리 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 -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 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 -

Subtask #6
0 / 22.0

# 결과 실행 시간 메모리 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 -

Subtask #7
0 / 4.0

# 결과 실행 시간 메모리 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 -

Subtask #8
0 / 3.0

# 결과 실행 시간 메모리 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 -