//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e2 + 2;
const int INF = 1e9 + 7;
int ans[MAXN], mx[MAXN][MAXN][2];
int dp[MAXN][MAXN][2], dp2[MAXN][MAXN][2];
bool adj[MAXN][MAXN];
int nex[MAXN][MAXN];
int n;
inline bool between(int l, int r, int x) {
if (l > r)
return l < x || x < r;
return l < x && x < r;
}
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 = dp[l][r][k];
ret = 0;
int lo = k ? r : l;
int hi = l ^ r ^ lo;
for (int i=1; i <= nex[r][0]; i++)
if (between(lo, hi, nex[r][i]))
ret = max(ret, max(solve(r, nex[r][i], k^1), solve(l, nex[r][i], k)) + 1);
return 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;
int lo = k ? r : l;
int hi = l ^ r ^ lo;
for (int i=1; i <= nex[l][0]; i++)
if (between(lo, hi, nex[l][i]))
ret = max(ret, f2(nex[l][i], r, k));
return dp2[l][r][k] = ret + 1;
}
int b[MAXN];
int main() {
memset(dp, -1, sizeof dp);
memset(dp2, -1, sizeof dp2);
int k;
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++) {
b[i] = i;
int x;
while (1) {
scanf("%d", &x);
if (x == 0)
break;
adj[i][x] = 1;
nex[i][++nex[i][0]] = x;
}
}
for (int i = 1; i <= n; i++)
for (int j=1; j <= nex[i][0]; j++)
ans[i] = max(ans[i], max(solve(i, nex[i][j], 0), solve(i, nex[i][j], 1)) + 1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
shuffle(b+1,b+n+1, rng);
if (k == 1) for (int ii = 1; ii <= n; ii++) {
int i = b[ii];
memset(mx, 0, sizeof mx);
for (int x = (i%n) + 1; x != i; x = (x%n) + 1)
for (int y = (x+1)%n + 1; y != i; y = (y%n) + 1) {
mx[x][y][0] = mx[x][(y+n-2)%n + 1][0];
if (adj[i][(y+n-2)%n + 1])
mx[x][y][0] = max(mx[x][y][0], solve(x,(y+n-2)%n + 1,0) + 1);
}
for (int x = (i+n-2)%n+1; x != i; x = (x-2+n)%n+1)
for (int y = (x+2*n-3)%n+1; y != i; y = (y-2+n)%n+1) {
mx[y][x][1] = mx[y%n+1][x][1];
if (adj[i][y%n+1])
mx[y][x][1] = max(mx[y][x][1], solve(x,y%n+1,1) + 1);
}
for (int l = i%n+1; l != (i+2*n-3)%n+1; l = (l%n) + 1)
for (int j = (l+1)%n+1; j != i; j = (j%n) + 1) {
if (adj[l][j])
ans[l] = max(ans[l], max(f2(j, i, 0) + mx[l][j][0], f2(j, i, 0) + mx[l][j][1]) + 1);
if (adj[j][l])
ans[j] = max(ans[j], max(f2(l, i, 1) + mx[l][j][0], f2(l, i, 1) + mx[l][j][1]) + 1);
}
if (ii > 420) break;
}
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 main()':
race.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &k);
~~~~~^~~~~~~~~~~~~~~~~
race.cpp:53:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
4344 KB |
Output is correct |
| 2 |
Correct |
9 ms |
6264 KB |
Output is correct |
| 3 |
Correct |
11 ms |
6392 KB |
Output is correct |
| 4 |
Correct |
13 ms |
6392 KB |
Output is correct |
| 5 |
Correct |
6 ms |
4472 KB |
Output is correct |
| 6 |
Correct |
20 ms |
6392 KB |
Output is correct |
| 7 |
Correct |
8 ms |
4476 KB |
Output is correct |
| 8 |
Correct |
29 ms |
6520 KB |
Output is correct |
| 9 |
Correct |
9 ms |
4472 KB |
Output is correct |
| 10 |
Correct |
18 ms |
4600 KB |
Output is correct |
| 11 |
Correct |
11 ms |
4600 KB |
Output is correct |
| 12 |
Correct |
237 ms |
6776 KB |
Output is correct |
| 13 |
Correct |
668 ms |
7036 KB |
Output is correct |
| 14 |
Correct |
59 ms |
5244 KB |
Output is correct |
| 15 |
Correct |
2714 ms |
7544 KB |
Output is correct |
| 16 |
Correct |
2775 ms |
7524 KB |
Output is correct |
| 17 |
Correct |
2758 ms |
7544 KB |
Output is correct |
| 18 |
Correct |
74 ms |
5496 KB |
Output is correct |
| 19 |
Correct |
2902 ms |
7480 KB |
Output is correct |
| 20 |
Correct |
2900 ms |
7544 KB |
Output is correct |
