Submission #703033

#TimeUsernameProblemLanguageResultExecution timeMemory
703033JosiaSailing Race (CEOI12_race)C++17
55 / 100
3081 ms16032 KiB
#include <bits/stdc++.h> #define int int64_t using namespace std; vector<vector<bool>> graph; // vector<vector<bool>> graphRev; int n; bool type; int DP1[500][500][2][2]; int DP2[500][500][2][2]; void init() { for (int i=0; i<500; i++) { for (int j = 0; j<500; j++) { for (int k = 0; k<2; k++) { for (int l = 0; l<2; l++) { DP1[i][j][k][l] = -1; DP2[i][j][k][l] = -1; } } } } } int dp1(int l, int r, bool pos, bool start) { if (DP1[l][r][pos][start] != -1) return DP1[l][r][pos][start]; int res = 0; for (int v = (l+1)%n; v!=r; v=(v+1)%n) { if (!graph[pos?r:l][v]) continue; // if (pos==0) { res = max(dp1(l, v, 1, 0)+1, res); res = max(dp1(v, r, 0, 0)+1, res); // } // if (pos==1) { // res = max(dp(l, v, 1, 0)+1, res); // res = max(dp(v, r, 0, 0)+1, res); // } } // cerr << l << " " << r << " " << res << "\n"; return DP1[l][r][pos][start] = res; } int dp2(int l, int r, bool pos, bool start) { if (DP2[l][r][pos][start] != -1) return DP2[l][r][pos][start]; int res = -2; if ((l+1)%n==r) res = 0; for (int v = (l+1)%n; v!=r; v=(v+1)%n) { if (!graph[pos?r:l][v]) continue; if (pos==0) { // res = max(dp2(l, v, 1, 0)+1, res); res = max(dp2(v, r, 0, 0)+1, res); } if (pos==1) { res = max(dp2(l, v, 1, 0)+1, res); // res = max(dp(v, r, 0, 0)+1, res); } } // cerr << l << " " << r << " " << res << "\n"; if (res == -1) res = -2; return DP2[l][r][pos][start] = res; } signed main() { cin.tie(0); ios_base::sync_with_stdio(0); init(); cin >> n; cin >> type; graph.assign(n,vector<bool>(n, 0)); for (int i = 0; i<n; i++) { int x; cin >> x; while (x!=0) { graph[i][x-1]=1; // graphRev[x-1][i]=1; cin >> x; } } int res = 0; int ind = -1; for (int i = 0; i<n; i++) { if (dp1(i, i, 0, 1) > res) { res = dp1(i, i, 0, 1); ind = i; } } if (type == 0) { cout << res << "\n" << ind+1 << "\n"; return 0; } for (int i = 0; i<n; i++) { for (int j = 0; j<n; j++) { int tmp = 2; if (dp2((j+n-1)%n, i, 1, 1) == -2) continue; tmp += dp2((j+n-1)%n, i, 1, 1); int posFirst = -1; for (int k = i; k != j; k=(k+1)%n) { if (graph[k][i]) posFirst = k; // cerr << k << " " << i << "\n"; } if (posFirst == -1) continue; int best = 0; for (int k = (i+1)%n; k != posFirst; k=(k+1)%n) { if (!graph[j][k]) continue; best = max(best, max(dp1(k, posFirst, 0, 1), dp1(i, k, 1, 1))); } tmp += best; // cerr << i << " " << j << " " << dp2((j+n-1)%n, i, 1, 1) << " " << tmp << "\n"; if (tmp > res) { ind = posFirst; res = tmp; } } } // cerr << "-------\n"; // for (int i = 0; i<n; i++) { // for (int j = 0; j<n; j++) { // dp2(i, j, 0, 0); // dp2(i, j, 1, 0); // dp2(i, j, 0, 1); // dp2(i, j, 1, 1); // } // } for (int i = 0; i<n; i++) { for (int j = 0; j<n; j++) { if ((i+n-j)%n < 2 || ((i+n-j)%n)-n > -2) continue; int tmp = 2; if (dp2((j+n-1)%n, i, 0, 1) == -2) continue; tmp += dp2((j+n-1)%n, i, 0, 1); int posFirst = -1; for (int k = j; k != i; k=(k+n-1)%n) { if (graph[k][j]) posFirst = k; // cerr << k << " " << i << "\n"; } if (posFirst == -1) continue; int best = 0; for (int k = (j+n-1)%n; k != posFirst; k=(k+n-1)%n) { if (!graph[j][k]) continue; best = max(best, max(dp1(posFirst, k, 1, 1), dp1(k, j, 0, 1))); } tmp += best; // cerr << i << " " << j << " " << dp2((j+n-1)%n, i, 0, 1) << " " << tmp << "\n"; if (tmp > res) { ind = posFirst; res = tmp; } } } cout << res << "\n" << ind+1 << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...