Submission #55224

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
55224	2018-07-06T12:35:48 Z	linkret	Sailing Race (CEOI12_race)	C++14	70 / 100	1387 ms	7244 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Incorrect	2 ms	616 KB	Output isn't correct
3	Incorrect	3 ms	812 KB	Output isn't correct
4	Correct	3 ms	940 KB	Output is correct
5	Correct	4 ms	1068 KB	Output is correct
6	Correct	5 ms	1196 KB	Output is correct
7	Correct	8 ms	1356 KB	Output is correct
8	Incorrect	9 ms	1484 KB	Output isn't correct
9	Correct	12 ms	1664 KB	Output is correct
10	Correct	43 ms	1848 KB	Output is correct
11	Correct	19 ms	1848 KB	Output is correct
12	Correct	76 ms	3256 KB	Output is correct
13	Incorrect	121 ms	4316 KB	Output isn't correct
14	Correct	141 ms	5604 KB	Output is correct
15	Incorrect	727 ms	6908 KB	Output isn't correct
16	Correct	1175 ms	7120 KB	Output is correct
17	Incorrect	769 ms	7120 KB	Output isn't correct
18	Correct	265 ms	7120 KB	Output is correct
19	Correct	1387 ms	7244 KB	Output is correct
20	Correct	1280 ms	7244 KB	Output is correct