Submission #55225

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
55225	2018-07-06T12:37:45 Z	linkret	Sailing Race (CEOI12_race)	C++14	40 / 100	1821 ms	7228 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][j];

					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

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Incorrect	2 ms	680 KB	Output isn't correct
3	Incorrect	2 ms	748 KB	Output isn't correct
4	Incorrect	4 ms	972 KB	Output isn't correct
5	Correct	4 ms	1148 KB	Output is correct
6	Incorrect	6 ms	1280 KB	Output isn't correct
7	Correct	12 ms	1408 KB	Output is correct
8	Incorrect	6 ms	1484 KB	Output isn't correct
9	Correct	13 ms	1616 KB	Output is correct
10	Correct	27 ms	1792 KB	Output is correct
11	Correct	16 ms	1792 KB	Output is correct
12	Incorrect	64 ms	3088 KB	Output isn't correct
13	Incorrect	117 ms	4144 KB	Output isn't correct
14	Correct	150 ms	5552 KB	Output is correct
15	Incorrect	1031 ms	7008 KB	Output isn't correct
16	Incorrect	1276 ms	7092 KB	Output isn't correct
17	Incorrect	1045 ms	7092 KB	Output isn't correct
18	Correct	253 ms	7092 KB	Output is correct
19	Incorrect	1499 ms	7228 KB	Output isn't correct
20	Incorrect	1821 ms	7228 KB	Output isn't correct