답안 #55217

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55217 2018-07-06T11:53:57 Z linkret Sailing Race (CEOI12_race) C++14
40 / 100
1144 ms 6396 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; 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;
}
# 결과 실행 시간 메모리 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