Submission #55217

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
55217	2018-07-06T11:53:57 Z	linkret	Sailing Race (CEOI12_race)	C++14	40 / 100	1144 ms	6396 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; j < n; j++) {
				for(int k : adj[j]) {
					int l = f[i][k];

					if(between(j, k, i) && l != -1) {
						int tmp;

						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 {

					}
				}
			}
		}
	}

	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	740 KB	Output isn't correct
3	Incorrect	2 ms	812 KB	Output isn't correct
4	Incorrect	3 ms	964 KB	Output isn't correct
5	Correct	4 ms	1024 KB	Output is correct
6	Incorrect	7 ms	1340 KB	Output isn't correct
7	Correct	8 ms	1360 KB	Output is correct
8	Incorrect	8 ms	1364 KB	Output isn't correct
9	Correct	15 ms	1492 KB	Output is correct
10	Correct	44 ms	1620 KB	Output is correct
11	Correct	21 ms	1620 KB	Output is correct
12	Incorrect	77 ms	2648 KB	Output isn't correct
13	Incorrect	133 ms	3668 KB	Output isn't correct
14	Correct	162 ms	4832 KB	Output is correct
15	Incorrect	705 ms	5868 KB	Output isn't correct
16	Incorrect	901 ms	6124 KB	Output isn't correct
17	Incorrect	646 ms	6124 KB	Output isn't correct
18	Correct	186 ms	6124 KB	Output is correct
19	Incorrect	975 ms	6396 KB	Output isn't correct
20	Incorrect	1144 ms	6396 KB	Output isn't correct