Submission #1294239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294239		uranium235	Sailing Race (CEOI12_race)	C++17	15 / 100	28 ms	4416 KiB

race

#include <bits/stdc++.h>
using namespace std;

template <class t> ostream& operator<<(ostream &l, const vector<t> &r) {
    l << "{";
    for (int i = 0; i + 1 < r.size(); i++) l << r[i] << ", ";
    if (!r.empty()) l << r.back();
    l << "}";
    return l;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    assert(k == 0);

    vector<vector<int>> adj(n);
    for (int i = 0; i < n; i++) {
        int x;
        while (true) {
            cin >> x;
            if (!x) break;
            assert(x - 1 != i);
            adj[i].push_back(x - 1);
        }
    }

    vector<vector<int>> dp(2 * n, vector<int>(2 * n));
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < n; j++) {
            int s = j, e = i + j - 1;
            for (int k : adj[s]) {
                if (k + n <= e) k += n;
                if (k < s || k > e) continue;

                // "enclose" the previous path
                if (k == e) {
                    dp[s][e] = max(dp[s][e], 1 + dp[e][s + 1]);
                } else {
                    // concat path
                    dp[s][e] = max(dp[s][e], 1 + dp[k][e]);
                }
            }

            for (int k : adj[e % n]) {
                if (k + n <= e) k += n;
                if (k < s || k > e) continue;
                
                if (k == s) {
                    dp[e][s] = max(dp[e][s], 1 + dp[s][e - 1]);
                } else {
                    dp[e][s] = max(dp[e][s], 1 + dp[k][s]);
                }
            }

            // cout << "dp " << s << " " << e << " " << dp[s][e] << " " << dp[e][s] << endl; 

            if (e < n) {
                dp[s + n][e + n] = dp[s][e];
                dp[e + n][s + n] = dp[e][s];
            }
        }
    }

    pair<int, int> ans;
    for (int i = 0; i < n; i++) {
        ans = max(ans, {dp[i][i + n - 1], i});
        ans = max(ans, {dp[i + n - 1][i], i == 0 ? (n - 1) : (i - 1)});
    }

    cout << ans.first << '\n' << (ans.second + 1) << '\n';
}

• Subtask 1: 15 / 100