Submission #321473

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
321473	2020-11-12T12:28:52 Z	MetB	Sailing Race (CEOI12_race)	C++14	5 / 100	1447 ms	7308 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] << ' ' << 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 (!dp[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

#	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	1516 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	228 ms	4588 KB	Output isn't correct
14	Incorrect	320 ms	5996 KB	Output isn't correct
15	Incorrect	1268 ms	7148 KB	Output isn't correct
16	Incorrect	1417 ms	7228 KB	Output isn't correct
17	Incorrect	1247 ms	7276 KB	Output isn't correct
18	Incorrect	645 ms	7308 KB	Output isn't correct
19	Incorrect	1447 ms	7228 KB	Output isn't correct
20	Incorrect	1434 ms	7228 KB	Output isn't correct