제출 #1259575

#제출 시각아이디문제언어결과실행 시간메모리
1259575mtshastaSailing Race (CEOI12_race)C++20
100 / 100
787 ms6560 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 500; int n, ai, dp1[MAXN][MAXN][2], dp2[MAXN][MAXN][2], dp3[MAXN][MAXN][2], b[MAXN][2]; bool k, adj[MAXN][MAXN]; array<int, 2> ans; void c(int l, int r, int a) { if (adj[l][r]) { dp1[l][r][a] = 1; dp2[l][r][a] = 1 + dp3[r][b[l][a]][a ^ 1]; } else dp1[l][r][a] = dp2[l][r][a] = -n; for (int k = b[l][a]; k != r; k = b[k][a]) { dp1[l][r][a] = max(dp1[l][k][a] + dp1[k][r][a], dp1[l][r][a]); dp2[l][r][a] = max(dp1[l][k][a] + dp2[k][r][a], dp2[l][r][a]); } dp3[l][r][a] = max(dp2[l][r][a], dp3[l][b[r][a ^ 1]][a]); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> k; for (int i = 0; i < n; i++) { cin >> ai; while (ai) { adj[i][ai - 1] = 1; cin >> ai; } b[i][0] = (i + n - 1) % n; b[i][1] = (i + 1) % n; } for (int l = 1; l < n; l++) { for (int i = 0; i < n; i++) { c(i, (i + l) % n, 1); c((i + l) % n, i, 0); } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < 2; k++) { ans = max({{dp2[i][j][k], i}, ans}); } } } if (k) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int a = 0; a < 2; a++) { if (dp1[i][j][a] <= 0) continue; int nx = b[j][a]; for (; nx != i && !adj[nx][i]; nx = b[nx][a]) ; if (nx != i) for (int l = b[nx][a]; l != i; l = b[l][a]) if (adj[j][l]) ans = max({{2 + dp1[i][j][a] + max(dp3[l][b[nx][a]][a ^ 1], dp3[l][b[i][a ^ 1]][a]), nx}, ans}); } } } } cout << ans[0] << "\n" << ans[1] + 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...