#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, k, q, type, edge[501][501], dp[501][501][2], dp1[501][501][2],
nx[501][2];
string s;
void solve(int l, int r, int x) {
if (edge[l][r]) {
dp[l][r][x] = 1;
dp1[l][r][x] = 1 + dp1[r][nx[l][x]][x ^ 1];
} else
dp[l][r][x] = dp1[l][r][x] = -1e9;
for (int m = nx[l][x]; m != r; m = nx[m][x]) {
dp[l][r][x] = max(dp[l][r][x], dp[l][m][x] + dp[m][r][x]);
dp1[l][r][x] = max(dp1[l][r][x], dp[l][m][x] + dp1[m][r][x]);
}
dp1[l][r][x] = max(dp1[l][r][x], dp1[l][nx[r][x ^ 1]][x]);
}
int main() {
cin >> n >> type;
for (int i = 0, x; i < n; i++) {
while (cin >> x && x-- != 0)
edge[i][x] = 1;
nx[i][0] = (i + 1) % n;
nx[i][1] = (i + n - 1) % n;
}
for (int d = 1; d < n; d++) {
for (int l = 0, r = (l + d) % n; l < n; l++) {
solve(l, (l + d) % n, 0);
solve((l + d) % n, l, 1);
}
}
pair<int, int> ans = {-1, 0};
for (int l = 0; l < n; l++)
for (int r = 0; r < n; r++)
for (int x = 0; x < 2; x++)
ans = max(ans, make_pair(dp1[l][r][x], l + 1));
if (type) {
for (int l = 0; l < n; l++)
for (int r = 0; r < n; r++)
for (int x = 0; x < 2; x++) {
if (dp[l][r][x] <= 0) continue;
int st = nx[r][x];
while (st != l && !edge[st][l])
st = nx[st][x];
if (st == l) continue;
for (int ed = nx[st][x]; ed != l; ed = nx[ed][x]) {
if (edge[r][ed]) {
int num = max(dp1[ed][nx[st][x]][x ^ 1],
dp1[ed][nx[l][x ^ 1]][x]);
ans = max(ans, make_pair(1 + dp[l][r][x] + 1 + num,
st + 1));
}
}
}
}
cout << ans.first << "\n" << ans.second << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |