Submission #321474

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
321474	2020-11-12T12:29:53 Z	MetB	Sailing Race (CEOI12_race)	C++14	5 / 100	1407 ms	7404 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 (!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

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