Submission #1266536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266536		kaiboy	Sailing Race (CEOI12_race)	C++20	100 / 100	1168 ms	3864 KiB

race

#pragma GCC optimize("O3")
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 500;

bool aa[N][N], bb[N][N];
int dp[N][N][2], dq[N][N], tt[N];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, c; cin >> n >> c;
	if (n == 1) {
		cout << "0\n";
		cout << "1\n";
		return 0;
	}
	for (int i = 0; i < n; i++)
		while (true) {
			int j; cin >> j, j--;
			if (j == -1)
				break;
			aa[i][j] = true;
		}
	for (int d = 1; d <= n; d++)
		for (int l = 0; l < n; l++) {
			int r = (l + d) % n;
			for (int h = 0; h < 2; h++) {
				int i = h ? r : l, x = 0;
				for (int j = l + 1 < n ? l + 1 : 0; j != r; j = j + 1 < n ? j + 1 : 0)
					if (aa[i][j])
						x = max(x, max(dp[l][j][1], dp[j][r][0]) + 1);
				dp[l][r][h] = x;
			}
		}
	int x_ = -1, s_ = -1;
	for (int s = 0; s < n; s++) {
		int x = dp[s][s][0];
		if (x_ < x)
			x_ = x, s_ = s;
	}
	if (!c) {
		cout << x_ << '\n';
		cout << s_ + 1 << '\n';
		return 0;
	}
	for (int s = 0; s < n; s++) {
		for (int i = 0, i_ = s; i < n; i++, i_ = i_ + 1 < n ? i_ + 1 : 0)
			for (int j = 0, j_ = s; j < n; j++, j_ = j_ + 1 < n ? j_ + 1 : 0)
				bb[i][j] = aa[i_][j_];
		dq[s][s] = tt[0] = 0;
		for (int i = 1; i < n; i++) {
			int x = -1;
			for (int j = 0; j < i; j++)
				if (bb[j][i] && tt[j] != -1)
					x = max(x, tt[j] + 1);
			dq[s][(s + i) % n] = tt[i] = x;
		}
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			if (i == j || dq[i][j] == -1)
				continue;
			int s = j + 1 < n ? j + 1 : 0;
			while (s != i && !aa[s][i])
				s = s + 1 < n ? s + 1 : 0;
			if (s == i)
				continue;
			int x = 0;
			for (int k = s + 1 < n ? s + 1 : 0; k != i; k = k + 1 < n ? k + 1 : 0)
				if (aa[j][k])
					x = max(x, max(dp[s][k][1], dp[k][i][0]) + 1);
			x += dq[i][j] + 1;
			if (x_ < x)
				x_ = x, s_ = s;
		}
	for (int s = 0; s < n; s++) {
		for (int i = 0, i_ = s; i < n; i++, i_ = (i_ ? i_ : n) - 1)
			for (int j = 0, j_ = s; j < n; j++, j_ = (j_ ? j_ : n) - 1)
				bb[i][j] = aa[i_][j_];
		dq[s][s] = tt[0] = 0;
		for (int i = 1; i < n; i++) {
			int x = -1;
			for (int j = 0; j < i; j++)
				if (bb[j][i] && tt[j] != -1)
					x = max(x, tt[j] + 1);
			dq[s][(s - i + n) % n] = tt[i] = x;
		}
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			if (i == j || dq[i][j] == -1)
				continue;
			int s = (j ? j : n) - 1;
			while (s != i && !aa[s][i])
				s = (s ? s : n) - 1;
			if (s == i)
				continue;
			int x = 0;
			for (int k = i + 1 < n ? i + 1 : 0; k != s; k = k + 1 < n ? k + 1 : 0)
				if (aa[j][k])
					x = max(x, max(dp[i][k][1], dp[k][s][0]) + 1);
			x += dq[i][j] + 1;
			if (x_ < x)
				x_ = x, s_ = s;
		}
	cout << x_ << '\n';
	cout << s_ + 1 << '\n';
	return 0;
}

• Subtask 1: 100 / 100