Submission #1106887

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1106887	2024-10-31T08:42:44 Z	Zero_OP	Sailing Race (CEOI12_race)	C++14	40 / 100	1058 ms	14524 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>> adj(N);
    vector<vector<bool>> e(N, vector<bool>(N));

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

    vector<vector<vector<int>>> f(N, vector<vector<int>>(N, vector<int>(2, -1)));

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

        for(int i = (l + 1) % N; i != r; i = (i + 1) % N){
            if(x == 0){
                if(e[l][i]){
                    maximize(ret, dp(l, i, 1) + 1);
                    maximize(ret, dp(i, r, 0) + 1);
                }
            } else{
                if(e[r][i]){
                    maximize(ret, dp(i, r, 0) + 1);
                    maximize(ret, dp(l, i, 1) + 1);
                }
            }
        }

        return ret;
    };

    pair<int, int> answer = {0, 0};
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            if(e[i][j]){
                maximize(answer, {dp(i, j, 1) + 1, i});
                maximize(answer, {dp(j, i, 0) + 1, i});
            }
        }
    }

    cout << answer.first << ' ' << answer.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	504 KB	Output isn't correct
5	Correct	2 ms	592 KB	Output is correct
6	Incorrect	2 ms	592 KB	Output isn't correct
7	Correct	5 ms	592 KB	Output is correct
8	Incorrect	3 ms	592 KB	Output isn't correct
9	Correct	8 ms	848 KB	Output is correct
10	Correct	13 ms	1020 KB	Output is correct
11	Correct	10 ms	1060 KB	Output is correct
12	Incorrect	56 ms	2640 KB	Output isn't correct
13	Incorrect	149 ms	5456 KB	Output isn't correct
14	Correct	331 ms	9296 KB	Output is correct
15	Incorrect	856 ms	14416 KB	Output isn't correct
16	Incorrect	922 ms	14416 KB	Output isn't correct
17	Incorrect	918 ms	14416 KB	Output isn't correct
18	Correct	573 ms	14328 KB	Output is correct
19	Incorrect	1058 ms	14416 KB	Output isn't correct
20	Incorrect	1018 ms	14524 KB	Output isn't correct