답안 #55223

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55223 2018-07-06T12:29:48 Z linkret Sailing Race (CEOI12_race) C++14
70 / 100
1323 ms 6268 KB
#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++) {
				if(i == j)
					continue;

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

					if(between(j, k, i)) 
						l = f[i][j];
					else
						l = f[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]);
						} 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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Incorrect 3 ms 740 KB Output isn't correct
3 Incorrect 3 ms 900 KB Output isn't correct
4 Correct 3 ms 960 KB Output is correct
5 Correct 5 ms 1348 KB Output is correct
6 Correct 7 ms 1348 KB Output is correct
7 Correct 11 ms 1348 KB Output is correct
8 Incorrect 8 ms 1348 KB Output isn't correct
9 Correct 10 ms 1468 KB Output is correct
10 Correct 26 ms 1596 KB Output is correct
11 Correct 14 ms 1600 KB Output is correct
12 Correct 54 ms 2796 KB Output is correct
13 Incorrect 104 ms 3708 KB Output isn't correct
14 Correct 161 ms 4724 KB Output is correct
15 Incorrect 659 ms 6012 KB Output isn't correct
16 Correct 850 ms 6268 KB Output is correct
17 Incorrect 830 ms 6268 KB Output isn't correct
18 Correct 244 ms 6268 KB Output is correct
19 Correct 1323 ms 6268 KB Output is correct
20 Correct 1139 ms 6268 KB Output is correct