Submission #775496

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
775496	2023-07-06T12:55:05 Z	NK_	Sailing Race (CEOI12_race)	C++17	100 / 100	779 ms	2568 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	528 KB	Output is correct
6	Correct	3 ms	468 KB	Output is correct
7	Correct	4 ms	596 KB	Output is correct
8	Correct	3 ms	596 KB	Output is correct
9	Correct	5 ms	712 KB	Output is correct
10	Correct	14 ms	724 KB	Output is correct
11	Correct	7 ms	724 KB	Output is correct
12	Correct	49 ms	1108 KB	Output is correct
13	Correct	83 ms	1492 KB	Output is correct
14	Correct	52 ms	1876 KB	Output is correct
15	Correct	495 ms	2448 KB	Output is correct
16	Correct	638 ms	2552 KB	Output is correct
17	Correct	530 ms	2388 KB	Output is correct
18	Correct	71 ms	2360 KB	Output is correct
19	Correct	767 ms	2568 KB	Output is correct
20	Correct	779 ms	2568 KB	Output is correct