oj.uz

Submission #775489

# Submission time Handle Problem Language Result Execution time Memory
775489 2023-07-06T12:43:36 Z NK_ Sailing Race (CEOI12_race) C++17
70 / 100
 1235 ms 41940 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;

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 6 ms 1108 KB Output is correct
8 Correct 5 ms 1400 KB Output is correct
9 Correct 13 ms 1612 KB Output is correct
10 Correct 21 ms 1996 KB Output is correct
11 Correct 11 ms 2028 KB Output is correct
12 Correct 65 ms 6868 KB Output is correct
13 Correct 131 ms 15188 KB Output is correct
14 Correct 129 ms 26776 KB Output is correct
15 Runtime error 805 ms 41760 KB Memory limit exceeded
16 Runtime error 1000 ms 41884 KB Memory limit exceeded
17 Runtime error 849 ms 41756 KB Memory limit exceeded
18 Runtime error 221 ms 41604 KB Memory limit exceeded
19 Runtime error 1178 ms 41932 KB Memory limit exceeded
20 Runtime error 1235 ms 41940 KB Memory limit exceeded