Submission #321477

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
321477	2020-11-12T12:36:08 Z	MetB	Sailing Race (CEOI12_race)	C++14	5 / 100	1327 ms	7276 KB

race

#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

#	Verdict	Execution time	Memory	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