Submission #775496

#	Time	Username	Problem	Language	Result	Execution time	Memory
775496		NK_	Sailing Race (CEOI12_race)	C++17	100 / 100	779 ms	2568 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;
const int nax = 505;
int dp[nax][nax][2];
int dst[nax][2];
int harbor[nax][2];


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

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

	for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) for(int k = 0; k < 2; k++) {
		dp[i][j][k] = -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) {
			return dp[l][r][d];
		}

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

		return dp[l][r][d] = best;
	};


	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(int i = 0; i < N; i++) for(int j = 0; j < 2; j++) {
				dst[i][j] = -INF;
				harbor[i][j] = -1;
			}

			for(int d = -1; d <= 1; d += 2) {
				int t = max(0, d);
				dst[l][t] = 0;
				for(int y = (l+d+N)%N; y != l; y = (y+d+N)%N) {
					for(auto v : adj[y]) dst[y][t] = max(dst[y][t], dst[v][t] + 1);
					for(auto v : adj[y]) if (harbor[v][t] == -1) harbor[v][t] = y;
				}
			}

			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[x][t];
						int fir = harbor[x][!t]; if (fir == -1) continue;
						int sec = x;

						if (between(l, sec, r) ^ between(l, fir, r)) { // CHECK IF IT ACTUALLY INTERSECTS
							// 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: 100 / 100