Submission #321467

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
321467	2020-11-12T12:19:27 Z	MetB	Sailing Race (CEOI12_race)	C++14	5 / 100	1364 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];

				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	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	1900 KB	Output is correct
11	Incorrect	6 ms	1772 KB	Output isn't correct
12	Incorrect	77 ms	3052 KB	Output isn't correct
13	Incorrect	227 ms	4460 KB	Output isn't correct
14	Incorrect	274 ms	5996 KB	Output isn't correct
15	Incorrect	1190 ms	7404 KB	Output isn't correct
16	Incorrect	1259 ms	7368 KB	Output isn't correct
17	Incorrect	1214 ms	7404 KB	Output isn't correct
18	Incorrect	606 ms	7268 KB	Output isn't correct
19	Incorrect	1352 ms	7396 KB	Output isn't correct
20	Incorrect	1364 ms	7404 KB	Output isn't correct