Submission #1266127

#TimeUsernameProblemLanguageResultExecution timeMemory
1266127kaiboySailing Race (CEOI12_race)C++20
In queue
0 ms0 KiB
#include <algorithm> #include <iostream> using namespace std; const int N = 500; bool aa[N][N]; int dp[N][N][2], dq[N][N]; int main() { ios_base::sync_with_stdio(false), cin.tie(NULL); int n, c; cin >> n >> c; if (n == 1) { cout << "0\n"; cout << "1\n"; return 0; } for (int i = 0; i < n; i++) while (true) { int j; cin >> j, j--; if (j == -1) break; aa[i][j] = true; } for (int d = 1; d <= n; d++) for (int l = 0; l < n; l++) { int r = (l + d) % n; for (int h = 0; h < 2; h++) { int i = h ? r : l, x = 0; for (int j = (l + 1) % n; j != r; j = (j + 1) % n) if (aa[i][j]) x = max(x, max(dp[l][j][1], dp[j][r][0]) + 1); dp[l][r][h] = x; } } int x_ = -1, s_ = -1; for (int s = 0; s < n; s++) { int x = dp[s][s][0]; if (x_ < x) x_ = x, s_ = s; } if (!c) { cout << x_ << '\n'; cout << s_ + 1 << '\n'; return 0; } for (int s = 0; s < n; s++) { dq[s][s] = 0; for (int i = (s + 1) % n; i != s; i = (i + 1) % n) { int x = -1; for (int j = s; j != i; j = (j + 1) % n) if (aa[j][i] && dq[s][j] != -1) x = max(x, dq[s][j] + 1); dq[s][i] = x; } } for (int i = 0; i < n; i++) for (int j = (i + 1) % n; j != i; j = (j + 1) % n) { if (dq[i][j] == -1) continue; int s = (j + 1) % n; while (s != i && !aa[s][i]) s = (s + 1) % n; if (s == i) continue; int x = 0; for (int k = (s + 1) % n; k != i; k = (k + 1) % n) if (aa[j][k]) x = max(x, max(dp[s][k][1], dp[k][i][0]) + 1); x += dq[i][j] + 1; if (x_ < x) x_ = x, s_ = s; } for (int s = 0; s < n; s++) { dq[s][s] = 0; for (int i = (s - 1 + n) % n; i != s; i = (i - 1 + n) % n) { int x = -1; for (int j = s; j != i; j = (j - 1 + n) % n) if (aa[j][i] && dq[s][j] != -1) x = max(x, dq[s][j] + 1); dq[s][i] = x; } } for (int i = 0; i < n; i++) for (int j = (i - 1 + n) % n; j != i; j = (j - 1 + n) % n) { if (dq[i][j] == -1) continue; int s = (j - 1 + n) % n; while (s != i && !aa[s][i]) s = (s - 1 + n) % n; if (s == i) continue; int x = 0; for (int k = (i + 1) % n; k != s; k = (k + 1) % n) if (aa[j][k]) x = max(x, max(dp[i][k][1], dp[k][s][0]) + 1); x += dq[i][j] + 1; if (x_ < x) x_ = x, s_ = s; } cout << x_ << '\n'; cout << s_ + 1 << '\n'; return 0; }