Submission #55224

#	Time	Username	Problem	Language	Result	Execution time	Memory
55224		linkret	Sailing Race (CEOI12_race)	C++14	70 / 100	1387 ms	7244 KiB

race

#include <bits/stdc++.h>

using namespace std;

const int maxn = 505, inf = 1e9;

int n, id;
vector<int> adj[maxn];
vector<int> radj[maxn];

bool between(int l, int r, int i) {
	if(l > r) {
		return i >= l || i <= r;
	} else {
		return i >= l && i <= r;
	}
}

int dist(int i, int j) {
	if(i <= j)
		return j - i;
	return n - i + j;
}

int dp[2][2][maxn][maxn];
int f[2][maxn][maxn];

int main() {
	ios_base::sync_with_stdio(false);

	cin >> n >> id;

	for(int i = 0, j; i < n; i++) {
		while(true) {
			cin >> j;
			if(!j) break;
			j--;
			adj[i].push_back(j);
			radj[j].push_back(i);
		}
	}

	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			f[0][i][j] = -1;
			f[1][i][j] = -1;

			for(int k : radj[i]) {
				if(between(j, i, k))
					continue;

				if(f[0][i][j] == -1)
					f[0][i][j] = k;

				if(dist(i, f[0][i][j]) < dist(i, k))
					f[0][i][j] = k;
			}

			for(int k : radj[i]) {
				if(between(i, j, k))
					continue;

				if(f[1][i][j] == -1)
					f[1][i][j] = k;

				if(dist(i, f[1][i][j]) > dist(i, k))
					f[1][i][j] = k;
			}
		}
	}

	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			dp[1][0][i][j] = -inf;
			dp[1][1][i][j] = -inf;
		}
	}

	for(int i = 0; i < n; i++) {
		dp[1][0][i][i] = 0;
		dp[1][1][i][i] = 0;
	}

	for(int len = 1; len < n; len++) {
		for(int i = 0; i < n; i++) {
			int j = (i + len) % n;
			
			for(int k : radj[j]) {
				if(between(i, j, k)) {
					dp[1][0][i][j] = max(dp[1][0][i][j], 1 + dp[1][0][i][k]);
				}
			}

			for(int k : radj[i]) {
				if(between(i, j, k)) {
					dp[1][1][i][j] = max(dp[1][1][i][j], 1 + dp[1][1][k][j]);
				}
			}

			for(int k : adj[i]) {
				if(between(i, j, k)) {
					dp[0][0][i][j] = max(dp[0][0][i][j], 1 + max(dp[0][1][(i + 1) % n][k], dp[0][0][k][j]));
				}
			}

			for(int k : adj[j]) {
				if(between(i, j, k)) {
					dp[0][1][i][j] = max(dp[0][1][i][j], 1 + max(dp[0][1][i][k], dp[0][0][k][(j - 1 + n) % n]));
				}
			}
		}
	}

	int mxm = 0, t = 0;

	for(int i = 0; i < n; i++) {
		int tmp = dp[0][0][i][(i - 1 + n) % n];
		if(tmp > mxm) {
			mxm = tmp;
			t = i;
		}
	}

	if(id) {
		for(int i = 0; i < n; i++) {
			for(int j = 0, l; j < n; j++) {
				if(i == j)
					continue;

				for(int k : adj[j]) {
					if(i == k || j == k)
						continue;

					if(between(j, k, i)) 
						l = f[0][i][j];
					else
						l = f[1][i][k];

					if(l == i || l == j || l == k || l == -1)
						continue;

					if(between(j, k, i)) {
						int tmp = 0;

						if(between(k, j, l)) {
							tmp = dp[1][1][j][i] + 2 + max(dp[0][1][(i + 1) % n][k], dp[0][0][k][l]);
						}
					
						if(tmp > mxm) {
							mxm = tmp;
							t = l;
						}
					} else {
						int tmp = 0;

						if(between(j, k, l)) {
							tmp = dp[1][0][i][j] + 2 + max(dp[0][0][k][(i - 1 + n) % n], dp[0][1][k][l]);
						}
						
						if(tmp > mxm) {
							mxm = tmp;
							t = l;
						}
					}
				}
			}
		}
	}

	cout << mxm << endl << t + 1 << endl;

	// for(int i = 0; i < n; i++) {
	// 	for(int j = 0; j < n; j++) {
	// 		int k = dp[0][1][i][j];
	// 		if(k < 0)
	// 			cout << 'x' << " ";
	// 		else
	// 			cout << k << " ";
	// 	}
	// 	cout << endl;
	// }

	// for(int i = 0; i < n; i++) {
	// 	for(int j = 0; j < n; j++) {
	// 		cout << f[i][j] << " ";
	// 	}
	// 	cout << endl;
	// }

	return 0;
}

• Subtask 1: 70 / 100