답안 #775489

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
775489	2023-07-06T12:43:36 Z	NK_	Sailing Race (CEOI12_race)	C++17	70 / 100	1235 ms	41940 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;

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

#	결과	실행 시간	메모리	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