#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 500, INF = 1e9;
int dp1[MAXN][MAXN][2], dp2[MAXN][MAXN][2], dp3[MAXN][MAXN][2], nx[MAXN][2];
bool adj[MAXN][MAXN];
array<int, 2> ans;
void dp(int l, int r, int x) {
if (adj[l][r]) {
dp1[l][r][x] = 1;
dp2[l][r][x] = 1 + dp3[r][nx[l][x]][x ^ 1];
} else
dp1[l][r][x] = dp2[l][r][x] = -INF;
for (int k = nx[l][x]; k != r; k = nx[k][x]) {
dp1[l][r][x] = max(dp1[l][k][x] + dp1[k][r][x], dp1[l][r][x]);
dp2[l][r][x] = max(dp1[l][k][x] + dp2[k][r][x], dp2[l][r][x]);
}
dp3[l][r][x] = max(dp2[l][r][x], dp3[l][nx[r][x ^ 1]][x]);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
bool type;
cin >> n >> type;
for (int i = 0, x; i < n; i++) {
while (cin >> x && x-- != 0) {
adj[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++, r = nx[r][0]) {
dp(l, r, 0);
dp(r, l, 1);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < 2; k++) {
ans = max({{dp2[i][j][k], i}, ans});
}
}
}
if (type) {
for (int l = 0; l < n; l++) {
for (int r = 0; r < n; r++) {
for (int x = 0; x < 2; x++) {
if (dp1[l][r][x] <= 0) continue;
int st = nx[r][x];
while (st != l && !adj[st][l]) {
st = nx[st][x];
}
if (st == l) continue;
for (int ed = nx[st][x]; ed != l; ed = nx[ed][x]) {
if (adj[r][ed]) {
int num = max(dp1[ed][nx[st][x]][x ^ 1],
dp1[ed][nx[l][x ^ 1]][x]);
ans = max(ans, {2 + dp3[l][r][x] + num, st});
}
}
}
}
}
}
cout << ans[0] << "\n" << ans[1] + 1;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |