Submission #775489

#	Time	Username	Problem	Language	Result	Execution time	Memory
775489		NK_	Sailing Race (CEOI12_race)	C++17	70 / 100	1235 ms	41940 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;

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

	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;
	};

	// K = 0 IS WORKING

	// 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

	V<V<V<int>>> dst(N, V<V<int>>(N, V<int>(2, -INF))); // 0 - -1 / 1 - 1
	V<V<V<int>>> harbor(N, V<V<int>>(N, V<int>(2, -1)));  // best harbor for y if edge point is x
	for(int x = 0; x < N; x++) for(int d = -1; d <= 1; d += 2) {
		int t = max(0, d);
		dst[x][x][t] = 0;
		for(int y = (x+d+N)%N; y != x; y = (y+d+N)%N) {
			for(auto v : adj[y]) dst[x][y][t] = max(dst[x][y][t], dst[x][v][t] + 1);

			for(auto v : adj[y]) if (harbor[x][v][t] == -1) harbor[x][v][t] = y;
		}
	}


	if (K == 0) {
		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;
	} else {
		int ans = -1, best = -1;
		for(int l = 0; l < N; l++) for(auto r : adj[l]) {
			for(int d = -1; d <= 1; d += 2) {
				int t = max(0, d);
				for (int x = (l+d+N)%N; x != r; x = (x+d+N)%N) {
					int ex = dst[l][x][t];
					int fir = harbor[l][x][!t]; if (fir == -1) continue;
					int sec = x;

					// cout << l << " " << r << " " << d << " " << x << " => " << ex << " " << fir << endl;

					if (between(l, sec, r) ^ between(l, fir, r)) { // CHECK IF IT ACTUALLY INTERSECTS
						// cout << l << " " << r << " => " << fir << " " << sec << endl;
						// CUT WITH fir
						int res1 = ex + (between(l, fir, r) ? DP(fir, r, 1) : DP(r, fir, 0));
						if (ans < res1) ans = res1, best = fir + 1;

						// CUT WITH sec
						int res2 = ex + (between(l, sec, r) ? DP(sec, r, 1) : DP(r, sec, 0));
						if (ans < res2) ans = res2, best = fir + 1;
					}
				}
			}
		}
		cout << ans + 2 << nl << best << nl;

	}

	
		

    return 0;
}

• Subtask 1: 70 / 100