# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1266127 | kaiboy | Sailing Race (CEOI12_race) | C++20 | 0 ms | 0 KiB |
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 500;
bool aa[N][N];
int dp[N][N][2], dq[N][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; j != r; j = (j + 1) % n)
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++) {
dq[s][s] = 0;
for (int i = (s + 1) % n; i != s; i = (i + 1) % n) {
int x = -1;
for (int j = s; j != i; j = (j + 1) % n)
if (aa[j][i] && dq[s][j] != -1)
x = max(x, dq[s][j] + 1);
dq[s][i] = x;
}
}
for (int i = 0; i < n; i++)
for (int j = (i + 1) % n; j != i; j = (j + 1) % n) {
if (dq[i][j] == -1)
continue;
int s = (j + 1) % n;
while (s != i && !aa[s][i])
s = (s + 1) % n;
if (s == i)
continue;
int x = 0;
for (int k = (s + 1) % n; k != i; k = (k + 1) % n)
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++) {
dq[s][s] = 0;
for (int i = (s - 1 + n) % n; i != s; i = (i - 1 + n) % n) {
int x = -1;
for (int j = s; j != i; j = (j - 1 + n) % n)
if (aa[j][i] && dq[s][j] != -1)
x = max(x, dq[s][j] + 1);
dq[s][i] = x;
}
}
for (int i = 0; i < n; i++)
for (int j = (i - 1 + n) % n; j != i; j = (j - 1 + n) % n) {
if (dq[i][j] == -1)
continue;
int s = (j - 1 + n) % n;
while (s != i && !aa[s][i])
s = (s - 1 + n) % n;
if (s == i)
continue;
int x = 0;
for (int k = (i + 1) % n; k != s; k = (k + 1) % n)
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;
}