oj.uz

답안 #321474

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
321474 2020-11-12T12:29:53 Z MetB Sailing Race (CEOI12_race) C++14
5 / 100
 1407 ms 7404 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] << ' ' << 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] << ' ' << ind + 1 << endl;
}

Subtask #1
5.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 640 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 4 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 1516 KB Output isn't correct
10 Correct 7 ms 1644 KB Output is correct
11 Incorrect 7 ms 1644 KB Output isn't correct
12 Incorrect 78 ms 3196 KB Output isn't correct
13 Incorrect 241 ms 4460 KB Output isn't correct
14 Incorrect 274 ms 5868 KB Output isn't correct
15 Incorrect 1294 ms 7228 KB Output isn't correct
16 Incorrect 1353 ms 7404 KB Output isn't correct
17 Incorrect 1327 ms 7276 KB Output isn't correct
18 Incorrect 613 ms 7276 KB Output isn't correct
19 Incorrect 1383 ms 7308 KB Output isn't correct
20 Incorrect 1407 ms 7228 KB Output isn't correct