Submission #1259606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259606		firegirlwaterboy	Sailing Race (CEOI12_race)	C++20	5 / 100	836 ms	6560 KiB

race

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 500, INF = 1e9;
int dp1[MAXN][MAXN][2], dp2[MAXN][MAXN][2], dp3[MAXN][MAXN][2], nx[MAXN][2];
bool adj[MAXN][MAXN];

void dp(int l, int r, int a) {
    if (adj[l][r]) {
        dp1[l][r][a] = 1;
        dp2[l][r][a] = 1 + dp3[r][nx[l][a]][a ^ 1];
    } else {
        dp1[l][r][a] = dp2[l][r][a] = -INF;
    }
    for (int k = nx[l][a]; k != r; k = nx[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][nx[r][a ^ 1]][a]);
}

void solve() {
    int n;
    bool task;
    cin >> n >> task;
    for (int i = 0; i < n; i++) {
        int ai;
        cin >> ai;
        while (ai) {
            adj[i][ai - 1] = true;
            cin >> ai;
        }
        nx[i][0] = (i + n - 1) % n, nx[i][1] = (i + 1) % n;
    }
    for (int d = 1; d < n; d++) {
        for (int l = 0, r = (l + d) % n; l < n; l++, r = nx[r][0]) {
            dp(l, r, 1), dp(r, l, 0);
        }
    }
    pii ans{-1, 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 (task) {
        for (int l = 0; l < n; l++) {
            for (int r = 0; r < n; r++) {
                for (int x = 0; x < 2; x++) {
                    if (dp1[l][r][x] <= 0) continue;
                    int st = nx[r][x];
                    while (st != l && !adj[st][l]) {
                        st = nx[st][x];
                    }
                    if (st == l) continue;
                    for (int ed = nx[st][x]; ed != l; ed = nx[ed][x]) {
                        if (adj[r][ed]) {
                            int num = max(dp1[ed][nx[st][x]][x ^ 1],
                                          dp1[ed][nx[l][x ^ 1]][x]);
                            ans = max(ans, {2 + dp3[l][r][x] + num, st});
                        }
                    }
                }
            }
        }
    }
    cout << ans.first << "\n" << ans.second + 1 << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

• Subtask 1: 5 / 100