#include<bits/stdc++.h>
using namespace std;
const int N = 505;
int n, tp, Next[N], Prev[N], dp[N][N][2], dp2[N][N][2];
bool M[N][N];
inline void smax(int &a, int b){a = max(a, b);}
int main()
{
scanf("%d%d", &n, &tp);
for (int i = 0; i < n; i++)
{
int a;
scanf("%d", &a);
while (a)
M[i][a - 1] = 1, scanf("%d", &a);
}
for (int i = 0; i < n - 1; i++)
Next[i] = i + 1;
Next[n - 1] = 0;
for (int i = 1; i < n; i++)
Prev[i] = i - 1;
Prev[0] = n - 1;
memset(dp, -63, sizeof(dp));
memset(dp2, -63, sizeof(dp2));
for (int i = 0; i < n; i++)
dp[i][i][0] = dp[i][i][1] = 0;
for (int len = 2; len <= n; len ++)
for (int l = 0; l < n; l ++)
{
int r = (l + len - 1) % n;
// 0
for (int j = Next[l]; j != Next[r]; j = Next[j])
if (M[l][j])
smax(dp[l][r][0], dp[j][r][0] + 1);
// 1
for (int j = l; j != r; j = Next[j])
if (M[r][j])
smax(dp[l][r][1], dp[l][j][1] + 1);
}
for (int i = 0; i < n; i++)
dp2[i][i][0] = dp2[i][i][1] = 0;
for (int len = 2; len <= n; len ++)
for (int l = 0; l < n; l ++)
{
int r = (l + len - 1) % n;
// 0
for (int j = Next[l]; j != Next[r]; j = Next[j])
if (M[l][j])
smax(dp2[l][r][0], max(dp2[j][r][0] + 1, dp2[Next[l]][j][1] + 1));
// 1
for (int j = l; j != r; j = Next[j])
if (M[r][j])
smax(dp2[l][r][1], max(dp2[l][j][1] + 1, dp2[j][Prev[r]][0] + 1));
}
/*while (1)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
a --; b --;
printf("%d ::\n", dp2[a][b][c]);
}*/
int Mx = -1, st = -1;
for (int l = 0; l < n; l ++)
for (int r = 0; r < n; r ++)
if (M[l][r])
{
bool w = (l < r);
if (Mx < max(dp2[Next[l]][r][w], dp2[r][Prev[l]][!w]))
Mx = max(dp2[Next[l]][r][w], dp2[r][Prev[l]][!w]), st = l;
}
if (!tp)
return !printf("%d\n%d\n", Mx, st + 1);
for (int b = 0; b < n; b ++)
for (int c = 0; c < n; c ++)
if (b != c)
{
int a = -1;
for (int i = Next[c]; i != b; i = Next[i])
if (M[i][b])
{
a = i;
break;
}
if (a == -1)
continue;
for (int d = Next[a]; d != b; d = Next[d])
{
if (!M[c][d])
continue;
int res = 2 + dp[b][c][0] + max(dp2[d][Prev[b]][0], dp2[Next[a]][d][1]);
if (Mx < res)
Mx = res, st = a;
}
}
for (int b = 0; b < n; b ++)
for (int c = 0; c < n; c ++)
if (b != c)
{
int a = -1;
for (int i = Prev[c]; i != b; i = Prev[i])
if (M[i][b])
{
a = i;
break;
}
if (a == -1)
continue;
for (int d = Prev[a]; d != b; d = Prev[d])
{
if (!M[c][d])
continue;
int res = 2 + dp[c][b][1] + max(dp2[Prev[b]][d][1], dp2[d][Next[a]][0]);
if (Mx < res)
Mx = res, st = a;
}
}
return !printf("%d\n%d\n", Mx, st + 1);
}
Compilation message
race.cpp: In function 'int main()':
race.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &tp);
~~~~~^~~~~~~~~~~~~~~~~
race.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a);
~~~~~^~~~~~~~~~
race.cpp:15:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
M[i][a - 1] = 1, scanf("%d", &a);
~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
4352 KB |
Output isn't correct |
| 2 |
Incorrect |
5 ms |
4352 KB |
Output isn't correct |
| 3 |
Correct |
6 ms |
4352 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
4352 KB |
Output isn't correct |
| 5 |
Correct |
7 ms |
4352 KB |
Output is correct |
| 6 |
Correct |
8 ms |
4352 KB |
Output is correct |
| 7 |
Incorrect |
9 ms |
4352 KB |
Output isn't correct |
| 8 |
Correct |
11 ms |
4480 KB |
Output is correct |
| 9 |
Incorrect |
14 ms |
4352 KB |
Output isn't correct |
| 10 |
Incorrect |
12 ms |
4352 KB |
Output isn't correct |
| 11 |
Incorrect |
20 ms |
4352 KB |
Output isn't correct |
| 12 |
Incorrect |
94 ms |
4452 KB |
Output isn't correct |
| 13 |
Incorrect |
245 ms |
4600 KB |
Output isn't correct |
| 14 |
Incorrect |
372 ms |
4608 KB |
Output isn't correct |
| 15 |
Incorrect |
1203 ms |
4708 KB |
Output isn't correct |
| 16 |
Incorrect |
1325 ms |
4856 KB |
Output isn't correct |
| 17 |
Correct |
1226 ms |
4708 KB |
Output is correct |
| 18 |
Incorrect |
630 ms |
4728 KB |
Output isn't correct |
| 19 |
Incorrect |
1450 ms |
4736 KB |
Output isn't correct |
| 20 |
Correct |
1490 ms |
4784 KB |
Output is correct |
