Submission #1259411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259411		mtshasta	Sailing Race (CEOI12_race)	C++20	100 / 100	812 ms	5332 KiB

race

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, k, q, type, edge[501][501], dp[501][501][2], dp1[501][501][2],
    nx[501][2];
string s;
void solve(int l, int r, int x) {
    if (edge[l][r]) {
        dp[l][r][x] = 1;
        dp1[l][r][x] = 1 + dp1[r][nx[l][x]][x ^ 1];
    } else
        dp[l][r][x] = dp1[l][r][x] = -1e9;
    for (int m = nx[l][x]; m != r; m = nx[m][x]) {
        dp[l][r][x] = max(dp[l][r][x], dp[l][m][x] + dp[m][r][x]);
        dp1[l][r][x] = max(dp1[l][r][x], dp[l][m][x] + dp1[m][r][x]);
    }
    dp1[l][r][x] = max(dp1[l][r][x], dp1[l][nx[r][x ^ 1]][x]);
}
int main() {
    cin >> n >> type;
    for (int i = 0, x; i < n; i++) {
        while (cin >> x && x-- != 0)
            edge[i][x] = 1;
        nx[i][0] = (i + 1) % n;
        nx[i][1] = (i + n - 1) % n;
    }
    for (int d = 1; d < n; d++) {
        for (int l = 0, r = (l + d) % n; l < n; l++) {
            solve(l, (l + d) % n, 0);
            solve((l + d) % n, l, 1);
        }
    }
    pair<int, int> ans = {-1, 0};
    for (int l = 0; l < n; l++)
        for (int r = 0; r < n; r++)
            for (int x = 0; x < 2; x++)
                ans = max(ans, make_pair(dp1[l][r][x], l + 1));
    if (type) {
        for (int l = 0; l < n; l++)
            for (int r = 0; r < n; r++)
                for (int x = 0; x < 2; x++) {
                    if (dp[l][r][x] <= 0) continue;
                    int st = nx[r][x];
                    while (st != l && !edge[st][l])
                        st = nx[st][x];
                    if (st == l) continue;
                    for (int ed = nx[st][x]; ed != l; ed = nx[ed][x]) {
                        if (edge[r][ed]) {
                            int num = max(dp1[ed][nx[st][x]][x ^ 1],
                                          dp1[ed][nx[l][x ^ 1]][x]);
                            ans = max(ans, make_pair(1 + dp[l][r][x] + 1 + num,
                                                     st + 1));
                        }
                    }
                }
    }
    cout << ans.first << "\n" << ans.second << "\n";
}

• Subtask 1: 100 / 100