oj.uz

Submission #775495

# Submission time Handle Problem Language Result Execution time Memory
775495 2023-07-06T12:52:48 Z NK_ Sailing Race (CEOI12_race) C++17
100 / 100
 812 ms 2580 KB 
// 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); // 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);
		}
	}

	for(int i = 0; i < nax; i++) for(int j = 0; j < nax; 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) {
			// 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(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;

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2260 KB Output is correct
2 Correct 1 ms 2260 KB Output is correct
3 Correct 1 ms 2260 KB Output is correct
4 Correct 2 ms 2260 KB Output is correct
5 Correct 2 ms 2260 KB Output is correct
6 Correct 3 ms 2260 KB Output is correct
7 Correct 4 ms 2260 KB Output is correct
8 Correct 4 ms 2336 KB Output is correct
9 Correct 5 ms 2260 KB Output is correct
10 Correct 14 ms 2388 KB Output is correct
11 Correct 7 ms 2260 KB Output is correct
12 Correct 45 ms 2352 KB Output is correct
13 Correct 82 ms 2356 KB Output is correct
14 Correct 52 ms 2364 KB Output is correct
15 Correct 475 ms 2468 KB Output is correct
16 Correct 624 ms 2568 KB Output is correct
17 Correct 480 ms 2464 KB Output is correct
18 Correct 64 ms 2388 KB Output is correct
19 Correct 812 ms 2580 KB Output is correct
20 Correct 742 ms 2568 KB Output is correct