#include <bits/stdc++.h>
using namespace std;
#define _ << " _ " <<
#define TRACE(x) cout << #x << " = " << x << endl
const int MaxN = 510;
int n, m;
int sol, start;
bool con[MaxN][MaxN];
int memoA[MaxN][MaxN][2], memoB[MaxN][MaxN][2];
int nxt(int i, int d) {
if (d == 1) return (i + 1) % n;
return (i - 1 + n) % n;
}
int dpA(int i, int j, int d) {
int& dp = memoA[i][j][d];
if (dp != -1) return dp;
if (i == j) dp = 1;
else if (con[i][j]) dp = 2;
else dp = 0;
for (int k = i; k != j; k = nxt(k, d))
if (con[k][j] && dpA(i, k, d) > 0) dp = max(dp, dpA(i, k, d) + 1);
return dp;
}
int dpB(int i, int j, int d) {
int& dp = memoB[i][j][d];
if (dp != -1) return dp;
dp = (i != j);
for (int k = i; k != j; k = nxt(k, d))
if (con[i][k]) {
dp = max(dp, dpB(k, j, d) + 1);
dp = max(dp, dpB(k, i, 1 - d) + 1);
}
return dp;
}
void check(int cnt, int s) {
if (cnt > sol) {
sol = cnt;
start = s;
}
}
void solveS(int x, int s, int d) {
int maxB = 0, t = -1;
for (int i = nxt(s, d); i != x; i = nxt(i, d)) {
if (con[s][i]) {
t = i;
check(dpA(t, x, d) + maxB + 1, s);
// TRACE(s _ t _ x _ i);
// TRACE(dpA(t, x, d) _ maxB);
// if (dpA(t, x, d) + maxB == 4) TRACE(s _ t _ x _ dpA(t, x, d) _ maxB);
// cout << endl;
}
if (con[x][i])
maxB = max(maxB, dpB(i, s, 1 - d));
}
}
void solveT(int x, int t, int d) {
int maxB = 0, s = -1;
for (int i = nxt(x, d); i != t; i = nxt(i, d))
if (con[i][t]) {
s = i;
break;
}
if (s == -1) return;
for (int i = nxt(s, d); i != t; i = nxt(i, d))
if (con[x][i])
maxB = max(maxB, dpB(i, t, d));
check(dpA(t, x, d) + maxB + 1, s);
//TRACE(x _ t _ s _ d);
//TRACE(dpA(t, x, d) _ maxB);
//cout << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
int j;
for (cin >> j; j != 0; cin >> j)
con[i][j - 1] = true;
for (int j = 0; j < n; j++)
for (int d : {0, 1})
memoA[i][j][d] = memoB[i][j][d] = -1;
}
/*
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int d : {0, 1})
TRACE(i _ j _ d _ dpA(i, j, d));
*/
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int d : {0, 1})
if (con[i][j]) check(dpB(j, i, d) + 1, i)/*, TRACE(i _ j _ d _ dpB(j, i, d))*/;
if (m == 1)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (i != j) {
solveS(i, j, 0);
solveS(i, j, 1);
solveT(i, j, 0);
solveT(i, j, 1);
}
cout << sol - 1 << "\n" << start + 1 << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
484 KB |
Output is correct |
3 |
Correct |
3 ms |
812 KB |
Output is correct |
4 |
Correct |
7 ms |
1124 KB |
Output is correct |
5 |
Correct |
5 ms |
1124 KB |
Output is correct |
6 |
Correct |
20 ms |
1192 KB |
Output is correct |
7 |
Correct |
10 ms |
1328 KB |
Output is correct |
8 |
Correct |
34 ms |
1328 KB |
Output is correct |
9 |
Correct |
17 ms |
1376 KB |
Output is correct |
10 |
Correct |
24 ms |
1376 KB |
Output is correct |
11 |
Correct |
21 ms |
1480 KB |
Output is correct |
12 |
Correct |
489 ms |
2324 KB |
Output is correct |
13 |
Correct |
1453 ms |
3292 KB |
Output is correct |
14 |
Correct |
684 ms |
4024 KB |
Output is correct |
15 |
Execution timed out |
3056 ms |
4836 KB |
Time limit exceeded |
16 |
Execution timed out |
3029 ms |
4836 KB |
Time limit exceeded |
17 |
Execution timed out |
3005 ms |
4836 KB |
Time limit exceeded |
18 |
Correct |
1192 ms |
4876 KB |
Output is correct |
19 |
Execution timed out |
3032 ms |
4876 KB |
Time limit exceeded |
20 |
Execution timed out |
3025 ms |
4876 KB |
Time limit exceeded |