Submission #1106828

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1106828	2024-10-31T07:16:09 Z	Zero_OP	Sailing Race (CEOI12_race)	C++14	10 / 100	3000 ms	18504 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<bool>> edges(N, vector<bool>(N, false));
    for(int i = 0; i < N; ++i){
        int j;
        while(cin >> j){
            if(!j) break;
            --j;
            edges[i][j] = true;
        }
    }

    vector<vector<vector<int>>> dp(N, vector<vector<int>>(N, vector<int>(2, -1)));
    //maximum paths without self-intersection for range [l, r] and end at l or r

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

    function<int(int, int, int)> solve = [&](int l, int r, int pos){
        if(dp[l][r][pos] != -1) return dp[l][r][pos];
        int& ret = dp[l][r][pos];
        ret = 0;

        if(!pos){
            if(l <= r){
                ///(l, r]
                for(int i = l + 1; i <= r; ++i){
                    if(edges[l][i]) maximize(ret, solve(i, r, 0) + 1);
                }
            } else{
                ///[0...r] and (l, N)
                for(int i = 0; i <= r; ++i){
                    if(edges[l][i]) maximize(ret, solve(i, r, 0) + 1);
                }

                for(int i = l + 1; i < N; ++i){
                    if(edges[l][i]) maximize(ret, solve(i, r, 0) + 1);
                }
            }
        } else{
            if(l <= r){
                ///[l...r)
                for(int i = l; i < r; ++i){
                    if(edges[r][i]) maximize(ret, solve(l, i, 1) + 1);
                }
            } else{
                ///[0...r) and [l, N)
                for(int i = 0; i < r; ++i){
                    if(edges[r][i]) maximize(ret, solve(l, i, 1) + 1);
                }

                for(int i = l; i < N; ++i){
                    if(edges[r][i]) maximize(ret, solve(l, i, 1) + 1);
                }
            }
        }

        cerr << "(" << l << ", " << r << ", " << pos << ") = " << ret << '\n';
        return ret;
    };

    ///caes no self-intersection
    int answer = 0, start = 0;
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            if(maximize(answer, solve(i, j, 0))) start = i;
            if(maximize(answer, solve(i, j, 1))) start = j;
        }
    }

    if(!K){
        cout << answer << '\n';
        cout << start + 1 << '\n';
        return 0;
    }

    return 0;
}

Subtask #1

10.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	336 KB	Output is correct
2	Incorrect	10 ms	480 KB	Unexpected end of file - int32 expected
3	Incorrect	22 ms	540 KB	Unexpected end of file - int32 expected
4	Incorrect	38 ms	580 KB	Unexpected end of file - int32 expected
5	Incorrect	62 ms	592 KB	Output isn't correct
6	Incorrect	88 ms	688 KB	Unexpected end of file - int32 expected
7	Incorrect	121 ms	788 KB	Output isn't correct
8	Incorrect	167 ms	1100 KB	Unexpected end of file - int32 expected
9	Incorrect	205 ms	936 KB	Output isn't correct
10	Correct	249 ms	1296 KB	Output is correct
11	Incorrect	250 ms	1276 KB	Output isn't correct
12	Incorrect	1044 ms	4020 KB	Unexpected end of file - int32 expected
13	Incorrect	2314 ms	8564 KB	Unexpected end of file - int32 expected
14	Execution timed out	3037 ms	13200 KB	Time limit exceeded
15	Execution timed out	3070 ms	18392 KB	Time limit exceeded
16	Execution timed out	3043 ms	18256 KB	Time limit exceeded
17	Execution timed out	3077 ms	18120 KB	Time limit exceeded
18	Execution timed out	3065 ms	18504 KB	Time limit exceeded
19	Execution timed out	3058 ms	18208 KB	Time limit exceeded
20	Execution timed out	3075 ms	18396 KB	Time limit exceeded