Submission #774679

#	Time	Username	Problem	Language	Result	Execution time	Memory
774679		NK_	Sailing Race (CEOI12_race)	C++17	40 / 100	128 ms	14160 KiB

race

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define f first
#define s second
#define mp make_pair

using pi = pair<int, int>;
template<class T> using V = vector<T>;

const int INF = 1e9 + 10;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, K; cin >> N >> K;
	assert(K == 0);

	V<V<int>> adj(N);
	for(int i = 0; i < N; i++) {
		int x = -1;
		while(1) {
			cin >> x; --x;
			if (x == -1) break;
			adj[i].pb(x);
		}
	}

	V<V<V<int>>> dp(N, V<V<int>>(N, V<int>(2, -1)));

	auto between = [&](int L, int M, int R) {
		if (L > R) R += N;
		if (L > M) M += N;
		return L < M && M < R;
	};

	function<int(int, int, int)> DP = [&](int l, int r, int d) {
		int x = !d ? l : r;

		if (dp[l][r][d]!= -1) {
			// cout << l << ", " << r << ", " << x << " => " << dp[l][r][d] << endl;
			return dp[l][r][d];
		}

		// cout << l << ", " << r << ", " << x << ", " << d << endl;

		int best = 0;
		for(auto y : adj[x]) {
			// cout << y << " -> " << between(l, y, r) << endl;
			if (between(l, y, r)) {
				// cout << "IN: " << y << endl;
				best = max(best, DP(l, y, 1) + 1); // CUT INTO [L, y]
				best = max(best, DP(y, r, 0) + 1); // CUT INTO [y, R]
			}
		}

		// cout << l << ", " << r << ", " << x << " => " << best << endl;
		return dp[l][r][d] = best;
	};

	// HANDLE K = 1
	// FIX LINE THAT CROSSES THE FIRST LINE

	// OBS: FOR A LINE TO ONLY CROSS THE FIRST LINE
	// THE RANGE SHOULD MOVE ONLY TOWARDS THE FIRST HARBORS

	// ITERATE OVER SECOND HARBOR (RIGHT POINT OF FIRST LINE)
	// FIND LONGEST PATH FROM START OF FIXED EDGE TO THE SECOND HARBOR (THAT WAS CHOSEN)
	// FIND FIRST HARBOR THAT MAXIMIZES SIZE OF RANGE THAT THE END OF THE FIXED EDGE HAS

	int ans = -1, best = -1;
	for(int l = 0; l < N; l++) for(auto r : adj[l]) {
		int res1 = DP(l, r, 1);
		if (ans < res1) ans = res1, best = l + 1;

		int res2 = DP(r, l, 0);
		if (ans < res2) ans = res2, best = l + 1;
	}

	cout << ans + 1 << nl << best << nl;
		

    return 0;
}

• Subtask 1: 40 / 100