Submission #1107230

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1107230	2024-11-01T03:41:30 Z	Zero_OP	Sailing Race (CEOI12_race)	C++14	40 / 100	1675 ms	29048 KB

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); //case init98uyr
            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 edges
                //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[to[k][bestS]][candidate][k ^ 1], max_dp[candidate][to[k ^ 1][i]][k]);
                        int solution = 1 + dp[i][j][k] + 1 + last;
                        maximize(res, {solution, bestS});
                    }
                }
            }
        }
    }

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

    return 0;
}

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Incorrect	1 ms	336 KB	Output isn't correct
3	Incorrect	1 ms	336 KB	Output isn't correct
4	Incorrect	1 ms	592 KB	Output isn't correct
5	Correct	2 ms	592 KB	Output is correct
6	Incorrect	3 ms	1020 KB	Output isn't correct
7	Correct	4 ms	1004 KB	Output is correct
8	Incorrect	5 ms	1104 KB	Output isn't correct
9	Correct	7 ms	1360 KB	Output is correct
10	Correct	8 ms	1616 KB	Output is correct
11	Correct	8 ms	1616 KB	Output is correct
12	Incorrect	64 ms	5040 KB	Output isn't correct
13	Incorrect	181 ms	10576 KB	Output isn't correct
14	Correct	267 ms	18644 KB	Output is correct
15	Incorrect	1096 ms	28988 KB	Output isn't correct
16	Incorrect	1242 ms	29048 KB	Output isn't correct
17	Incorrect	1229 ms	29008 KB	Output isn't correct
18	Correct	593 ms	28844 KB	Output is correct
19	Incorrect	1675 ms	29008 KB	Output isn't correct
20	Incorrect	1505 ms	29008 KB	Output isn't correct