Submission #1106854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106854		Zero_OP	Sailing Race (CEOI12_race)	C++14	10 / 100	741 ms	14172 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;
        }
    }

    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 / 100