Submission #1106828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106828		Zero_OP	Sailing Race (CEOI12_race)	C++14	10 / 100	3077 ms	18504 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<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 / 100