Submission #55222

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
55222	2018-07-06T12:28:15 Z	linkret	Sailing Race (CEOI12_race)	C++14	55 / 100	3000 ms	6224 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[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[i][j] = -1;

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

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

				if(dist(i, f[i][j]) < dist(i, k))
					f[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++) {
				for(int k : adj[j]) {
					if(between(j, k, i)) 
						l = f[i][j];
					else
						l = f[i][k];

					set<int> st;
					st.insert(i);
					st.insert(j);
					st.insert(k);
					st.insert(l);

					if(st.size() != 4 || 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]);
						} else {
							// tmp = dp[1][1][j][i] + 2 + max(dp[0][1][(i + 1) % n][k], dp[0][0][k][(j - 1 + n) % n]);
						}

						// if(tmp == 6) {
						// 	cout << i << " " << j << " " << k << ", l je " << l << endl;
						// }
					
						if(tmp > mxm) {
							mxm = tmp;
							t = l;
						}
					} else {
						// 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]);
						// } else {
						// 	// tmp = dp[1][1][j][i] + 2 + max(dp[0][1][(i + 1) % n][k], dp[0][0][k][(j - 1 + n) % n]);
						// }

						// // if(tmp == 6) {
						// // 	cout << i << " " << j << " " << k << ", l je " << l << endl;
						// // }
						
						// 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

55.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Incorrect	23 ms	744 KB	Output isn't correct
3	Incorrect	3 ms	872 KB	Output isn't correct
4	Correct	6 ms	872 KB	Output is correct
5	Correct	4 ms	1036 KB	Output is correct
6	Correct	17 ms	1224 KB	Output is correct
7	Correct	10 ms	1288 KB	Output is correct
8	Incorrect	17 ms	1304 KB	Output isn't correct
9	Correct	12 ms	1432 KB	Output is correct
10	Correct	24 ms	1560 KB	Output is correct
11	Correct	14 ms	1692 KB	Output is correct
12	Correct	373 ms	2632 KB	Output is correct
13	Incorrect	772 ms	3784 KB	Output isn't correct
14	Correct	173 ms	4816 KB	Output is correct
15	Execution timed out	3059 ms	5984 KB	Time limit exceeded
16	Execution timed out	3053 ms	6224 KB	Time limit exceeded
17	Execution timed out	3042 ms	6224 KB	Time limit exceeded
18	Correct	204 ms	6224 KB	Output is correct
19	Execution timed out	3053 ms	6224 KB	Time limit exceeded
20	Execution timed out	3047 ms	6224 KB	Time limit exceeded