Submission #1106854

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1106854	2024-10-31T08:01:33 Z	Zero_OP	Sailing Race (CEOI12_race)	C++14	10 / 100	741 ms	14172 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;
        }
    }

    const int inf = 1e6;
    vector<vector<vector<int>>> dp(N, vector<vector<int>>(N, vector<int>(2, -inf)));
    //maximum paths without self-intersection for range [l, r] and counterclockwise or clockwise

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

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

    auto next = [&](int pos){
        return (pos == N - 1 ? 0 : pos + 1);
    };

    auto prev = [&](int pos){
        return (pos == 0 ? N - 1 : pos - 1);
    };

    auto solve = [&](int l, int r, int pos){
        if(!pos){
            for(int x = next(l);; x = next(x)){
                maximize(dp[l][r][pos], dp[l][x][pos] + dp[x][r][pos]);
                if(x == r) return;
            }
        } else{
            for(int x = prev(r);; x = prev(x)){
                maximize(dp[l][r][pos], dp[x][r][pos] + dp[l][x][pos]);
                if(x == l) return;
            }
        }
    };

    for(int len = 1; len < N; ++len){
        for(int l = 0; l < N; ++l){
            int r_next = (l + len) % N;
            int r_prev = ((l - len) % N + N) % N;

            solve(l, r_next, 0);
            solve(l, r_next, 1);
            solve(r_prev, l, 0);
            solve(r_prev, l, 1);
        }
    }

    ///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, dp[i][j][0])) start = i;
            if(maximize(answer, dp[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	1 ms	336 KB	Output is correct
2	Incorrect	1 ms	336 KB	Unexpected end of file - int32 expected
3	Incorrect	1 ms	336 KB	Unexpected end of file - int32 expected
4	Incorrect	1 ms	336 KB	Unexpected end of file - int32 expected
5	Incorrect	1 ms	592 KB	Output isn't correct
6	Incorrect	2 ms	592 KB	Unexpected end of file - int32 expected
7	Incorrect	2 ms	592 KB	Output isn't correct
8	Incorrect	3 ms	592 KB	Unexpected end of file - int32 expected
9	Incorrect	4 ms	848 KB	Output isn't correct
10	Correct	5 ms	848 KB	Output is correct
11	Incorrect	5 ms	848 KB	Output isn't correct
12	Incorrect	39 ms	2640 KB	Unexpected end of file - int32 expected
13	Incorrect	139 ms	5248 KB	Unexpected end of file - int32 expected
14	Incorrect	353 ms	9328 KB	Output isn't correct
15	Incorrect	741 ms	14096 KB	Unexpected end of file - int32 expected
16	Incorrect	727 ms	14160 KB	Unexpected end of file - int32 expected
17	Incorrect	692 ms	14172 KB	Unexpected end of file - int32 expected
18	Incorrect	652 ms	14160 KB	Output isn't correct
19	Incorrect	688 ms	14160 KB	Unexpected end of file - int32 expected
20	Incorrect	646 ms	14160 KB	Unexpected end of file - int32 expected