Submission #1107238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107238		Zero_OP	Sailing Race (CEOI12_race)	C++14	100 / 100	1497 ms	28920 KiB

race

#include <bits/stdc++.h>

using namespace std;

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            return a = b, true;
        } return false;
    }

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

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int N, K;
    cin >> N >> K;

    vector<vector<int>> e(N, vector<int>(N));
    for(int i = 0, j = 0; i < N; ++i){
        while(cin >> j){
            if(!j) break;
            --j;
            e[i][j] = 1;
        }
    }

    const int inf = 1e9;
    vector<vector<vector<int>>> dp(N, vector<vector<int>>(N, vector<int>(2, -inf)));
    vector<vector<vector<int>>> max_dp(N, vector<vector<int>>(N, vector<int>(2, -inf)));

    //dp[l][r][k] = maximum paths if we start at l, end at r and moving around range [l...r] in k-wise
    //max_dp[l][r][k] = maximum paths if we start at l end at somewhere but still moving around range [l...r] in k-wise

    for(int i = 0; i < N; ++i){
        dp[i][i][0] = dp[i][i][1] = max_dp[i][i][0] = max_dp[i][i][1] = 0;
    }

    vector<vector<int>> to(2, vector<int>(N));
    for(int i = 0; i < N; ++i){
        to[0][i] = (i + 1) % N;
        to[1][i] = (i + N - 1) % N;
    }

    auto solve = [&](int l, int r, int k){
        if(e[l][r]){
            maximize(dp[l][r][k], 1); //base-case
            maximize(max_dp[l][r][k], max_dp[r][to[k][l]][k ^ 1] + 1);  //case go back but not cut [l...r - 1]
        }

        for(int nxt = to[k][l]; nxt != r; nxt = to[k][nxt]){
            if(e[l][nxt]){
                maximize(dp[l][r][k], dp[l][nxt][k] + dp[nxt][r][k]);
                maximize(max_dp[l][r][k], dp[l][nxt][k] + max_dp[nxt][r][k]);
            }
        }

        maximize(max_dp[l][r][k], max_dp[l][to[k ^ 1][r]][k]);
    };

    for(int len = 1; len < N; ++len){
        for(int l = 0, r = len; l < N; ++l, r = (r + 1) % N){
            solve(l, r, 0);
            solve(r, l, 1);
        }
    }

    pair<int, int> res = {0, 0};
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            for(int k = 0; k < 2; ++k){
                maximize(res, make_pair(max_dp[i][j][k], i));
            }
        }
    }

    if(!K){
        cout << res.first << ' ' << res.second + 1 << '\n';
        return 0;
    }

    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            for(int k = 0; k < 2; ++k){
                if(dp[i][j][k] <= 0) continue;

                int bestS = to[k][j];
                while(bestS != i && !e[bestS][i]) bestS = to[k][bestS];
                if(bestS == i) continue;

                //just consider the first pos that in range [j+1...N-1] u [0...i - 1] that have edge with e[pos][i]
                //because when we move the j up, the range [i...j] will be extended and the max_dp[i][j][k] <= max_dp[i][to[k][j]][k]

                for(int candidate = to[k][bestS]; candidate != i; candidate = to[k][candidate]){ //choose the T
                    if(e[j][candidate]){ //S -> i -> ... -> j -> T -> ...
                        int last = max(max_dp[candidate][to[k][bestS]][k ^ 1], max_dp[candidate][to[k ^ 1][i]][k]); //some last paths
                        int solution = 1 + dp[i][j][k] + 1 + last;
                        maximize(res, {solution, bestS});
                    }
                }
            }
        }
    }

    cout << res.first << ' ' << res.second + 1 << '\n';

    return 0;
}

• Subtask 1: 100 / 100