#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 5e2 + 5;
const double eps = 1e-9;
int ans[MAXN], mx[MAXN][MAXN][2];
int dp[MAXN][MAXN][2], dp2[MAXN][MAXN][2];
bool adj[MAXN][MAXN];
int n;
int pr(int& x)
{
x--;
if (x < 1) x += n;
}
int nx(int& x)
{
x++;
if (x > n) x -= n;
}
int norm(int x)
{
if (x < 1) return x + n;
if (x > n) return x - n;
return x;
}
int solve(int l, int r, int k) // path ends at r, interval at l
{
if (dp[l][r][k] != -1)
return dp[l][r][k];
int ret = 0;
if (k) { // ccw
for (int i = norm(r + 1); i != l; nx(i))
if (adj[r][i])
ret = max(ret, max(solve(r, i, 0), solve(l, i, 1)) + 1);
} else { // cw
for (int i = norm(l + 1); i != r; nx(i))
if (adj[r][i])
ret = max(ret, max(solve(r, i, 1), solve(l, i, 0)) + 1);
}
return dp[l][r][k] = ret;
}
int f2(int l, int r, int k)
{
if (l == r)
return 0;
if (dp2[l][r][k] != -1)
return dp2[l][r][k];
int ret = adj[l][r] ? 0 : -INF;
if (k) {
for (int i = norm(r + 1); i != l; nx(i))
if (adj[l][i])
ret = max(ret, f2(i, r, 1));
} else {
for (int i = norm(l + 1); i != r; nx(i))
if (adj[l][i])
ret = max(ret, f2(i, r, 0));
}
return dp2[l][r][k] = ret + 1;
}
int main()
{
for (int i = 0; i < MAXN; i++)
for (int j = 0; j < MAXN; j++)
dp[i][j][0] = dp[i][j][1] = -1,
dp2[i][j][0] = dp2[i][j][1] = -1;
int k;
ni(n), ni(k);
for (int i = 1; i <= n; i++)
{
for (;;)
{
int x;
ni(x);
if (x == 0)
break;
adj[i][x] = 1;
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
if (!adj[i][j])
continue;
ans[i] = max(ans[i], solve(i, j, 0) + 1);
ans[i] = max(ans[i], solve(i, j, 1) + 1);
}
for (int i = 1; k == 1 && i <= n; i++)
{
memset(mx, 0, sizeof mx);
for (int x = norm(i + 1); x != i; nx(x))
for (int y = norm(x + 2); y != i; nx(y))
if (adj[i][norm(y - 1)])
mx[x][y][0] = max(solve(x, norm(y - 1), 0) + 1, mx[x][norm(y - 1)][0]);
else
mx[x][y][0] = max(0, mx[x][norm(y - 1)][0]);
for (int x = norm(i - 1); x != i; pr(x))
for (int y = norm(x - 2); y != i; pr(y))
if (adj[i][norm(y + 1)])
mx[y][x][1] = max(solve(x, norm(y + 1), 1) + 1, mx[norm(y + 1)][x][1]);
else
mx[y][x][1] = max(0, mx[norm(y + 1)][x][1]);
for (int l = norm(i + 1); l != norm(i - 2); nx(l))
for (int j = norm(l + 2); j != i; nx(j))
if (adj[l][j])
{
ans[l] = max(ans[l], f2(j, i, 0) + mx[l][j][0] + 1);
ans[l] = max(ans[l], f2(j, i, 0) + mx[l][j][1] + 1);
}
for (int l = norm(i + 1); l != norm(i - 2); nx(l))
for (int j = norm(l + 2); j != i; nx(j))
if (adj[j][l])
{
ans[j] = max(ans[j], f2(l, i, 1) + mx[l][j][0] + 1);
ans[j] = max(ans[j], f2(l, i, 1) + mx[l][j][1] + 1);
}
}
int ind = 0;
for (int i = 1; i <= n; i++)
if (ans[ind] < ans[i])
ind = i;
printf("%d\n%d\n", ans[ind], ind);
return 0;
}
Compilation message
race.cpp: In function 'int pr(int&)':
race.cpp:39:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
race.cpp: In function 'int nx(int&)':
race.cpp:45:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
race.cpp: In function 'int main()':
race.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
ni(n), ni(k);
^
race.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
race.cpp:7:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#define ni(n) scanf("%d", &(n))
~~~~~^~~~~~~~~~~~
race.cpp:103:13: note: in expansion of macro 'ni'
ni(x);
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4344 KB |
Output is correct |
| 2 |
Correct |
10 ms |
6504 KB |
Output is correct |
| 3 |
Correct |
12 ms |
6504 KB |
Output is correct |
| 4 |
Correct |
16 ms |
6548 KB |
Output is correct |
| 5 |
Correct |
8 ms |
6548 KB |
Output is correct |
| 6 |
Correct |
21 ms |
6588 KB |
Output is correct |
| 7 |
Correct |
11 ms |
6588 KB |
Output is correct |
| 8 |
Correct |
30 ms |
6848 KB |
Output is correct |
| 9 |
Correct |
14 ms |
6848 KB |
Output is correct |
| 10 |
Correct |
11 ms |
6848 KB |
Output is correct |
| 11 |
Correct |
14 ms |
6848 KB |
Output is correct |
| 12 |
Correct |
167 ms |
6956 KB |
Output is correct |
| 13 |
Correct |
574 ms |
7156 KB |
Output is correct |
| 14 |
Correct |
140 ms |
7156 KB |
Output is correct |
| 15 |
Correct |
2920 ms |
7236 KB |
Output is correct |
| 16 |
Correct |
2679 ms |
7480 KB |
Output is correct |
| 17 |
Correct |
2649 ms |
7556 KB |
Output is correct |
| 18 |
Correct |
238 ms |
7556 KB |
Output is correct |
| 19 |
Execution timed out |
3035 ms |
7768 KB |
Time limit exceeded |
| 20 |
Execution timed out |
3016 ms |
7808 KB |
Time limit exceeded |
