oj.uz

답안 #321477

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
321477 2020-11-12T12:36:08 Z MetB Sailing Race (CEOI12_race) C++14
5 / 100
 1327 ms 7276 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 2000000;
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;

int path[500][500][2], dp[500][500][2], dp_max[500][500][2];

int g[500][500], k;
int ans[500], n, m, nx[500][2];


void f_edge (int l, int r, int dir) {
	path[l][r][dir] = 1;
	dp[l][r][dir] = 1 + dp_max[r][nx[l][dir]][!dir];
}

void f (int l, int r, int dir) {
	for (int k = nx[l][dir]; k != r; k = nx[k][dir]) {
		path[l][r][dir] = max (dp[l][r][dir], path[l][k][dir] + path[k][r][dir]);
		dp[l][r][dir] = max (dp[l][r][dir], path[l][k][dir] + dp[k][r][dir]);
	}

	dp_max[l][r][dir] = max (dp[l][r][dir], dp_max[l][nx[r][!dir]][dir]);
}

int main () {
	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		int x;
		while (cin >> x && x) {
			g[i][x-1] = 1;
		}

		nx[i][0] = (i + 1) % n;
		nx[i][1] = i ? i - 1 : n - 1;
	}

	for (int k = 1; k < n; k++)
		for (int i = 0; i < n; i++) {
			int l = i, r = (i + k) % n;
			if (g[l][r]) f_edge (l, r, 0);
			if (g[r][l]) f_edge (r, l, 1);
			f (l, r, 0);
			f (r, l, 1);
		}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			for (int dir = 0; dir < 2; dir++)
				ans[i] = max (ans[i], dp[i][j][dir]);

	if (!k) {
		int ind = max_element(ans, ans + n) - ans;
		cout << ans[ind] << '\n' << ind + 1 << endl;
		return 0;
	}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			for (int dir = 0; dir < 2; dir++) {
				int k = nx[j][dir];

				if (!path[i][j][dir]) continue;

				while (k != i && !g[k][i]) k = nx[k][dir];

				if (k == i) continue;

				for (int l = nx[k][dir]; l != i; l = nx[l][dir]) {
					int ans_l = max(dp_max[l][nx[k][dir]][!dir], dp_max[l][nx[i][!dir]][dir]);
					if (g[j][l]) ans[k] = max (ans[k], 2 + path[i][j][dir] + ans_l);
					//cout << k << ' ' << i << ' ' << j << ' ' << l << ' ' << 2 + path[i][j][dir] + ans_l << endl;
				}

			}

	int ind = max_element(ans, ans + n) - ans;
	cout << ans[ind] << '\n' << ind + 1 << endl;
}

Subtask #1
5.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Incorrect 1 ms 620 KB Output isn't correct
3 Incorrect 1 ms 748 KB Output isn't correct
4 Incorrect 2 ms 876 KB Output isn't correct
5 Incorrect 2 ms 1004 KB Output isn't correct
6 Incorrect 3 ms 1132 KB Output isn't correct
7 Incorrect 3 ms 1260 KB Output isn't correct
8 Incorrect 6 ms 1388 KB Output isn't correct
9 Incorrect 5 ms 1536 KB Output isn't correct
10 Correct 7 ms 1644 KB Output is correct
11 Incorrect 6 ms 1644 KB Output isn't correct
12 Incorrect 78 ms 3180 KB Output isn't correct
13 Incorrect 222 ms 4460 KB Output isn't correct
14 Incorrect 273 ms 5996 KB Output isn't correct
15 Incorrect 1220 ms 7276 KB Output isn't correct
16 Incorrect 1317 ms 7276 KB Output isn't correct
17 Incorrect 1197 ms 7276 KB Output isn't correct
18 Incorrect 595 ms 7180 KB Output isn't correct
19 Incorrect 1327 ms 7276 KB Output isn't correct
20 Incorrect 1290 ms 7148 KB Output isn't correct