Submission #127041

#TimeUsernameProblemLanguageResultExecution timeMemory
127041eriksuenderhaufSailing Race (CEOI12_race)C++11
5 / 100
3069 ms7544 KiB
//#pragma GCC optimize("O3") #include <bits/stdc++.h> #define fmax(x,y) (x) ^ (((x) ^ (y)) & -((x) < (y))) 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 = fmax(ret, fmax(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 = fmax(ret, f2(nex[l][i], r, k)); return dp2[l][r][k] = ret + 1; } 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++) { 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] = fmax(ans[i], fmax(solve(i, nex[i][j], 0), solve(i, nex[i][j], 1)) + 1); if (k == 1) for (int i = 1; i <= n; i++) { 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] = fmax(mx[x][y][0], dp[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] = fmax(mx[y][x][1], dp[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] = fmax(ans[l], fmax(f2(j, i, 0) + mx[l][j][0], f2(j, i, 0) + mx[l][j][1]) + 1); if (adj[j][l]) ans[j] = fmax(ans[j], fmax(f2(l, i, 1) + mx[l][j][0], f2(l, i, 1) + mx[l][j][1]) + 1); } if (ans[i] == n) 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 (stderr)

race.cpp: In function 'int solve(int, int, int)':
race.cpp:27:85: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
             ret = fmax(ret, fmax(solve(r, nex[r][i], k^1),  solve(l, nex[r][i], k)) + 1);
                                                                                     ^
race.cpp:3:34: note: in definition of macro 'fmax'
 #define fmax(x,y) (x) ^ (((x) ^ (y)) & -((x) < (y)))
                                  ^
race.cpp:27:85: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
             ret = fmax(ret, fmax(solve(r, nex[r][i], k^1),  solve(l, nex[r][i], k)) + 1);
                                                                                     ^
race.cpp:3:49: note: in definition of macro 'fmax'
 #define fmax(x,y) (x) ^ (((x) ^ (y)) & -((x) < (y)))
                                                 ^
race.cpp: In function 'int main()':
race.cpp:60:88: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
             ans[i] = fmax(ans[i], fmax(solve(i, nex[i][j], 0), solve(i, nex[i][j], 1)) + 1);
                                                                                        ^
race.cpp:3:34: note: in definition of macro 'fmax'
 #define fmax(x,y) (x) ^ (((x) ^ (y)) & -((x) < (y)))
                                  ^
race.cpp:60:88: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
             ans[i] = fmax(ans[i], fmax(solve(i, nex[i][j], 0), solve(i, nex[i][j], 1)) + 1);
                                                                                        ^
race.cpp:3:49: note: in definition of macro 'fmax'
 #define fmax(x,y) (x) ^ (((x) ^ (y)) & -((x) < (y)))
                                                 ^
race.cpp:79:102: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
                     ans[l] = fmax(ans[l], fmax(f2(j, i, 0) + mx[l][j][0], f2(j, i, 0) + mx[l][j][1]) + 1);
                                                                                                      ^
race.cpp:3:34: note: in definition of macro 'fmax'
 #define fmax(x,y) (x) ^ (((x) ^ (y)) & -((x) < (y)))
                                  ^
race.cpp:79:102: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
                     ans[l] = fmax(ans[l], fmax(f2(j, i, 0) + mx[l][j][0], f2(j, i, 0) + mx[l][j][1]) + 1);
                                                                                                      ^
race.cpp:3:49: note: in definition of macro 'fmax'
 #define fmax(x,y) (x) ^ (((x) ^ (y)) & -((x) < (y)))
                                                 ^
race.cpp:81:102: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
                     ans[j] = fmax(ans[j], fmax(f2(l, i, 1) + mx[l][j][0], f2(l, i, 1) + mx[l][j][1]) + 1);
                                                                                                      ^
race.cpp:3:34: note: in definition of macro 'fmax'
 #define fmax(x,y) (x) ^ (((x) ^ (y)) & -((x) < (y)))
                                  ^
race.cpp:81:102: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
                     ans[j] = fmax(ans[j], fmax(f2(l, i, 1) + mx[l][j][0], f2(l, i, 1) + mx[l][j][1]) + 1);
                                                                                                      ^
race.cpp:3:49: note: in definition of macro 'fmax'
 #define fmax(x,y) (x) ^ (((x) ^ (y)) & -((x) < (y)))
                                                 ^
race.cpp:47: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:51:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...