Submission #1294429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294429		uranium235	Sailing Race (CEOI12_race)	C++17	75 / 100	389 ms	8952 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;
}

void cmax(int &a, int b) {
    if (b > a) a = b;
}

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

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

    // assert(k == 0);

    vector<vector<int>> adj(n), radj(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);
            radj[x - 1].push_back(i);
        }
    }

    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;
            dp[s][e] = dp[s][e - 1];
            dp[e][s] = dp[e][s + 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) {
                    cmax(dp[s][e], 1 + dp[e][s + 1]);
                } else {
                    // concat path
                    cmax(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) {
                    cmax(dp[e][s], 1 + dp[s][e - 1]);
                } else {
                    cmax(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];
            }
        }
    }

    vector<vector<int>> dp1(2 * n, vector<int>(2 * n, -1));
    for (int i = 0; i < n; i++) {
        for (int j : adj[i]) {
            dp1[i][j] = dp1[i + n][j + n] = 1;
            // pointing right
            if (j > i) {
                dp[i + n][j] = 1;
            } else {
                // pointing left
                dp[i][j + n] = 1;
            }
        }
        dp1[i][i] = dp1[i + n][i + n] = 0;
    }
    for (int i = 3; 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 || dp1[k][e] == -1) continue;
                cmax(dp1[s][e], 1 + dp1[k][e]);
            }

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

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

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

    vector<int> best(2 * n), valid(2 * n, -1);
    for (int i = 0; i < n; i++) {
        // if (i != 2) continue;
        for (int &j : radj[i]) {
            if (j < i) j += n;
        }
        sort(radj[i].begin(), radj[i].end());
        // cout << i << " " << radj[i] << endl;

        int ptr = 0;
        for (int j = i + 1; j < i + n; j++) {
            if (ptr < radj[i].size() && radj[i][ptr] == j) {
                for (int k = j + 1; k < i + n; k++) {
                    // j -> i -> whatever transitioned to valid[k] -> terminal
                    if (valid[k] != -1) {
                        int ts = max(dp[k][i + n - 1], dp[k][j + 1]) + valid[k];
                        // cout << "forward " << i << " " << j << " " << k << " " << ts << endl;
                        cmax(best[j], ts);
                    }
                }
                ptr++;
            }
            
            for (int k : adj[j % n]) {
                if (k < j + 1) k += n;
                // point to other half of circle
                if (k < j + 1 || k >= i + n || dp1[i][j] == -1) continue;
                cmax(valid[k], 2 + dp1[i][j]);
                assert(i <= k && k < i + n);
            }
        }
        assert(ptr == radj[i].size());
        fill(valid.begin(), valid.end(), -1);
        
        reverse(radj[i].begin(), radj[i].end());
        ptr = 0;
        for (int j = i + n - 1; j > i; j--) {
            if (ptr < radj[i].size() && radj[i][ptr] == j) {
                for (int k = j - 1; k > i; k--) {
                    // j -> i -> whatever transitioned to valid[k] -> terminal
                    if (valid[k] != -1) {
                        int ts = max(dp[k][i + 1], dp[k][j - 1]) + valid[k];
                        // cout << "rev " << i << " " << j << " " << k << " " << ts << " " << valid[k] << endl;;
                        cmax(best[j], ts);
                    }
                }
                ptr++;
            }
            
            for (int k : adj[j % n]) {
                if (k <= i) k += n;
                // point to other half of circle
                if (k <= i || k >= j || dp1[i + n][j] == -1) continue;
                
                // cout << "transition " << j << " " << k << " " << dp1[i][j] << endl;
                cmax(valid[k], 2 + dp1[i + n][j]);
                assert(i <= k && k < i + n);
            }
        }
        assert(ptr == radj[i].size());
        fill(valid.begin(), valid.end(), -1);
    }

    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)});
    }

    if (k) {
        for (int i = 0; i < 2 * n; i++) {
            ans = max(ans, {best[i], i % n});
        }
    }

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

• Subtask 1: 75 / 100